Por favor ayuda con un programa en C, números primos

[rod89]

tienen razón, mejor aprender

[crack81]

tu codigo espero te sirva y practica mas

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include <stdlib.h>

void SumaDePrimos(int x){
 int cont=0,suma=0;

 for(int i=x;i>=1;i--){
   for(int j=i;j>=1;j--){
       if(i%j==0){cont++;}
   }
   if(cont==2 or cont==1){
       suma=suma+i;
       if(suma<x){printf("%d ",i); }
       else if(suma==x){printf("%d ",i);  break; }
       else if(suma>x){suma=suma-i;}
   }
   cont=0;
 }
}

int main(){
 int x;

 printf("Ingrese un valor \n");
 scanf("%d",&x);

 SumaDePrimos(x);


return 0;}

[leosansan]

tu codigo espero te sirva y practica mas

Sólo le veo un "pero" a tu propuesta y es que si introduces 123456789  sencillamente se eterniza la respuesta. El problema radica en que después de encontrar el primo mayor, 123456761, sigue comprobando con el 123456760, 123456759, ...... y como  ves son muchos millones de primos a comprobar hasta llegar al 23.

La modificación que propongo lo que hace es, después de localizar al primo mayor más próximo al número introducido, es continuar comprobando desde el número introducido menos el mayor  primo calculado es decir: 12346789 - 123456761 = 28 e inferiores. Como ves se pasa de comprobar millones de números a unas pocas decenas lo que redunda en una mayor velocidad:  

Código (cpp) [Seleccionar] Expandir

void SumaDePrimos ( int num ) {
 int i , j , flag = 0 ,cont = 0 , suma = 0 ;
 for( i = num ; i >= 1 ; i-- ) {
   for ( j = i ; j >= 1 ; j-- )
      if ( i % j == 0 )
        cont++ ;
   if( cont == 2 || cont == 1 ) {
     suma += i ;
     if ( suma < num )
       printf ( "%d " , i ) ;
     else if ( suma == num ) {
       printf ( "%d " , i ) ;
       break;
     }
     else if ( suma > num )
       suma -= i ;
     if ( flag == 0 ) /* AQUI ESTA LA DIFERENCIA */
       i = num - i , flag = 1 ;
   }
   cont=0;
 }
}

Evidentemente se puede mejorar con sucesivas aproximaciones pero no es plan de hacer la tarea totalmente.

¡¡¡¡ Saluditos! ..... !!!!

[crack81]

Tienes una razón barbara y que la verdad que como explicas se reduciría el tiempo enormemente.

Esto le servirá mucho  a nuestro compañero pero hay recordad que esta es su tarea nosotros damos una posible solución.

Pero a un así me gusto tu idea leosansan saludos...

[leosansan]

..................................................
Pero a un así me gusto tu idea leosansan saludos...

Me alegra tu opinión y , efectivamente se puede mejorar pero tal como indicas, no es plan de hacerle la tarea con virguerias.   

Un fuerte saludo amigo crack81.

¡¡¡¡ Saluditos! ..... !!!!

[avesudra]

Me alegra tu opinión y , efectivamente se puede mejorar pero tal como indicas, no es plan de hacerle la tarea con virguerias.   

Un fuerte saludo amigo crack81.

¡¡¡¡ Saluditos! ..... !!!!

Se puede afinar incluso un poquito más, descartando los impares del iterador. Pero no sé si poner el codigo, por lo de la tarea y eso..

[crack81]

como dijo avesudra se puede afinar mas y lo hice quitando todos los numeros pares mayores a 2 con esto se reducen en 50% la velocidad de procesamiento

si alguien quiere ver cuanto mejora el rendimiento en su maquina les dejo el codigo completo les da el tiempo de procesamiento en milisegundos

mi version original con una cifra de 10000000 casi se quedaba congelada la maquina
con el arreglo de leosansan tarda unos 3319 milisegundos
y descartando los pares unos 1572 milisegundos

esto puedo variar por la velocidad de la maquina donde se realize aun asi les dejo el codigo completo para que hagan sus pruebas

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include <stdlib.h>
#include <windows.h>

void SumaDePrimos(int x){
 int cont=0,suma=0,flag=0;

 for(int i=x;i>=1;i--){
  if((i%2==0) and (i>2)){continue;}
   for(int j=i;j>=1;j--){
       if(i%j==0){cont++;}
   }
   if(cont==2 or cont==1){
       suma=suma+i;
       if(suma<x){printf("%d ",i);}
       else if(suma==x){printf("%d ",i); break; }
       else if(suma>x){suma=suma-i;}

       if(flag==0){i=x-i; flag=1;}
   }
   cont=0;
 }
}

double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b)
{
 LARGE_INTEGER freq;
 QueryPerformanceFrequency(&freq);
 return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart;
}

int main(){
 int x;
 LARGE_INTEGER t_ini, t_fin;
 double secs;

 printf("Ingrese un valor \n");
 scanf("%d",&x);

 QueryPerformanceCounter(&t_ini);
 SumaDePrimos(x);
 QueryPerformanceCounter(&t_fin);

 secs = performancecounter_diff(&t_fin, &t_ini);
 printf("\n%.16g milliseconds\n", secs * 1000.0);


return 0;}

[avesudra]

Poneis los códigos tan inentendibles que casi no puedo leerlos jajaja dejo el mío:

EDITO: CORREGIDO GRACIAS crack81 por avisar.

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>

/**
*  \brief Función que calcula los primos que hay que sumar para llegar a un
*         numero.
*  \param number Numero al que hay que calcularle esos primos.
*/
void sumOfPrimes(uint64_t number);

/**
*  \brief Función que determina si un numero es primo o no lo es.
*  \param number Numero al que hay que determinarle su primalidad.
*  \return Esta función devolvera 1 si el numero es primo o 0 si no lo es.
*/
int  isPrime    (uint64_t number);

int main(int argc, char** argv)
{
    uint64_t number;
    printf("Introduzca un numero: ");
    scanf("%llu", &number);
    sumOfPrimes(number);
    return 0;
}


void sumOfPrimes(uint64_t number)
{
    // Si el numero es primo la suma ya esta hecha.
    if(isPrime(number))
        printf(" %llu", number);
    else
    {
        uint64_t sum = 0;           // Variable para albergar la suma que vamos
                                    // realizando.
        uint64_t iterator = number;  // Iterador de numeros primos.
        /* Si el iterador es par lo disminuimos en una unidad, porque un numero
         * par nunca va a ser primo y así ganamos eficiencia.
         */

        if(iterator%2 == 0)
                    --iterator;
        while(sum != number)
        {
            if(isPrime(iterator))
            {
                sum += iterator;
                printf(" %llu", iterator);
                iterator = number - sum;
                if(iterator%2 == 0)
                    --iterator;
            }
            /* Decrementamos iterator en dos porque un numero par no es primo y
             * por tanto no nos interesa.
             */
            else
                iterator -= 2;
        }
    }
}
int  isPrime    (uint64_t number)
{
    // El uno es primo.
    if(number == 1)
        return 1;
    // El dos es primo.
    if(number == 2)
        return 1;
    // Todos los numeros pares no son primos.
    if(number % 2 == 0)
        return 0;
    uint64_t sqr = (uint64_t) sqrt(number);

    /*  Si el numero que da la raiz es par, lo decrementamos en una unidad pues
     *  solo nos interesan los numeros impares, ya que un numero impar no es di
     *  visible por un numero par.
     */
    if(sqr % 2 == 0)
        --sqr;

    while (sqr > 1)
    {
        if( number % sqr == 0)
            return 0;
        sqr -= 2;
    }
    return 1;
}

[crack81]

avesudra revisa tu programa porque se bloquea si pones 27 o un numero mayor a 10,000 se mete en un bucle infinito no se cual pueda ser el error porque ahora no tengo tiempo

y la funcion que puse en mi codigo la "performancecounter_diff" solo es para medir el tiempo que tarda la aplicacion pero la puedes quitar que solo es para fines demostrativos

[leosansan]

EDITADO con una sensible mejoría.

como dijo avesudra se puede afinar mas y lo hice quitando todos los numeros pares mayores a 2 con esto se reducen en 50% la velocidad de procesamiento

si alguien quiere ver cuanto mejora el rendimiento en su maquina les dejo el codigo completo les da el tiempo de procesamiento en milisegundos

mi version original con una cifra de 10000000 casi se quedaba congelada la maquina
con el arreglo de leosansan tarda unos 3319 milisegundos
y descartando los pares unos 1572 milisegundos

No me gusta en general  el uso de las operaciones "%"  y "sqrt" por su costo y en lo posible evito su uso. No es que esté mal pero si puedo evitarlas mejor que mejor.

Aquí una salida, como indica crack81, para 10 000 000:

Código (cpp) [Seleccionar] Expandir

Ingrese un valor :
10000000
9999991 7 2
274.1995607633197 milliseconds

Como se observa he bajado el valor de crack81 de 1572 ms a tan solo 274 ms.  

Y respetando la idea original de crack81 ahí va la función que logra lo anterior:

Código (cpp) [Seleccionar] Expandir

void SumaDePrimos ( int num ) {
  int i , i2 , j , num1 , flag = 0 ,cont = 0 , suma = 0 ;
  num1 = ( num % 2 == 0 ) ? num - 1 : num ; /* TOMO EL IMPAR SI NO LO ES */
  for( i = num1 ; i >= -2 ;  i -= 2 ) { /* VOY DE DOS EN DOS Y EVITO LA OPERACION % */
    if ( i == 1 )  i = 2 ;   /* ¡¡¡¡¡¡ */
    if ( i == - 2 )  i = 1 ; /* ¡¡¡¡¡¡ */
    i2 = i * i ; /* EVITO LA OPERACION SQRT */
    for ( j = 1 ; j <= i2 ; j += 2 ) {
      if ( i % j == 0 ) {
         cont++ ;
         if ( cont == 3 ) /* SI OCURRE NO ES PRIMO Y CORTO EL BUCLE */
           break ;
       }
    }
    if ( cont == 2 || cont == 1 ) {
      suma += i ;
      if ( suma < num )
        printf ("%d " , i ) ;
      else if ( suma == num ) {
        printf ("%d " , i ) ;
        break;
      }
      else if ( suma > num )
        suma -= i ;
      if ( flag == 0 ) /* TOMO EL IMPAR SI NO LO ES */
        i = num1 - i + 1 , flag = 1 ;
    }
    cont=0;
  }
}

¡¡¡¡ Saluditos! ..... !!!!