elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Por favor ayuda con un programa en C, números primos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: Por favor ayuda con un programa en C, números primos  (Leído 6,234 veces)
rod89

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Por favor ayuda con un programa en C, números primos
« en: 8 Noviembre 2014, 05:42 am »

tienen razón, mejor aprender


« Última modificación: 9 Noviembre 2014, 17:39 pm por Eternal Idol » En línea

crack81

Desconectado Desconectado

Mensajes: 222



Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #1 en: 8 Noviembre 2014, 07:11 am »

tu codigo espero te sirva y practica mas

Código
  1. #include<stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void SumaDePrimos(int x){
  5.  int cont=0,suma=0;
  6.  
  7.  for(int i=x;i>=1;i--){
  8.    for(int j=i;j>=1;j--){
  9.        if(i%j==0){cont++;}
  10.    }
  11.    if(cont==2 or cont==1){
  12.        suma=suma+i;
  13.        if(suma<x){printf("%d ",i); }
  14.        else if(suma==x){printf("%d ",i);  break; }
  15.        else if(suma>x){suma=suma-i;}
  16.    }
  17.    cont=0;
  18.  }
  19. }
  20.  
  21. int main(){
  22.  int x;
  23.  
  24.  printf("Ingrese un valor \n");
  25.  scanf("%d",&x);
  26.  
  27.  SumaDePrimos(x);
  28.  
  29.  
  30. return 0;}


« Última modificación: 8 Noviembre 2014, 07:18 am por crack81 » En línea

Si C/C++ es el padre de los lenguajes entonces ASM es dios.
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #2 en: 8 Noviembre 2014, 16:51 pm »

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
  1. void SumaDePrimos ( int num ) {
  2.  int i , j , flag = 0 ,cont = 0 , suma = 0 ;
  3.  for( i = num ; i >= 1 ; i-- ) {
  4.    for ( j = i ; j >= 1 ; j-- )
  5.       if ( i % j == 0 )
  6.         cont++ ;
  7.    if( cont == 2 || cont == 1 ) {
  8.      suma += i ;
  9.      if ( suma < num )
  10.        printf ( "%d " , i ) ;
  11.      else if ( suma == num ) {
  12.        printf ( "%d " , i ) ;
  13.        break;
  14.      }
  15.      else if ( suma > num )
  16.        suma -= i ;
  17.      if ( flag == 0 ) /* AQUI ESTA LA DIFERENCIA */
  18.        i = num - i , flag = 1 ;
  19.    }
  20.    cont=0;
  21.  }
  22. }


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

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


« Última modificación: 8 Noviembre 2014, 16:58 pm por leosansan » En línea

crack81

Desconectado Desconectado

Mensajes: 222



Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #3 en: 8 Noviembre 2014, 17:02 pm »

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...
En línea

Si C/C++ es el padre de los lenguajes entonces ASM es dios.
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #4 en: 8 Noviembre 2014, 17:06 pm »

..................................................
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! ..... !!!!


En línea

avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #5 en: 8 Noviembre 2014, 18:14 pm »

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..
En línea

Regístrate en
crack81

Desconectado Desconectado

Mensajes: 222



Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #6 en: 8 Noviembre 2014, 18:48 pm »

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
  1. #include<stdio.h>
  2. #include <stdlib.h>
  3. #include <windows.h>
  4.  
  5. void SumaDePrimos(int x){
  6.  int cont=0,suma=0,flag=0;
  7.  
  8.  for(int i=x;i>=1;i--){
  9.   if((i%2==0) and (i>2)){continue;}
  10.    for(int j=i;j>=1;j--){
  11.        if(i%j==0){cont++;}
  12.    }
  13.    if(cont==2 or cont==1){
  14.        suma=suma+i;
  15.        if(suma<x){printf("%d ",i);}
  16.        else if(suma==x){printf("%d ",i); break; }
  17.        else if(suma>x){suma=suma-i;}
  18.  
  19.        if(flag==0){i=x-i; flag=1;}
  20.    }
  21.    cont=0;
  22.  }
  23. }
  24.  
  25. double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b)
  26. {
  27.  LARGE_INTEGER freq;
  28.  QueryPerformanceFrequency(&freq);
  29.  return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart;
  30. }
  31.  
  32. int main(){
  33.  int x;
  34.  LARGE_INTEGER t_ini, t_fin;
  35.  double secs;
  36.  
  37.  printf("Ingrese un valor \n");
  38.  scanf("%d",&x);
  39.  
  40.  QueryPerformanceCounter(&t_ini);
  41.  SumaDePrimos(x);
  42.  QueryPerformanceCounter(&t_fin);
  43.  
  44.  secs = performancecounter_diff(&t_fin, &t_ini);
  45.  printf("\n%.16g milliseconds\n", secs * 1000.0);
  46.  
  47.  
  48. return 0;}


En línea

Si C/C++ es el padre de los lenguajes entonces ASM es dios.
avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #7 en: 8 Noviembre 2014, 19:01 pm »

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

EDITO: CORREGIDO GRACIAS crack81 por avisar.

Código
  1. #include <stdio.h>
  2. #include <stdint.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5.  
  6. /**
  7.  *  \brief Función que calcula los primos que hay que sumar para llegar a un
  8.  *         numero.
  9.  *  \param number Numero al que hay que calcularle esos primos.
  10.  */
  11. void sumOfPrimes(uint64_t number);
  12.  
  13. /**
  14.  *  \brief Función que determina si un numero es primo o no lo es.
  15.  *  \param number Numero al que hay que determinarle su primalidad.
  16.  *  \return Esta función devolvera 1 si el numero es primo o 0 si no lo es.
  17.  */
  18. int  isPrime    (uint64_t number);
  19.  
  20. int main(int argc, char** argv)
  21. {
  22.    uint64_t number;
  23.    printf("Introduzca un numero: ");
  24.    scanf("%llu", &number);
  25.    sumOfPrimes(number);
  26.    return 0;
  27. }
  28.  
  29.  
  30. void sumOfPrimes(uint64_t number)
  31. {
  32.    // Si el numero es primo la suma ya esta hecha.
  33.    if(isPrime(number))
  34.        printf(" %llu", number);
  35.    else
  36.    {
  37.        uint64_t sum = 0;           // Variable para albergar la suma que vamos
  38.                                    // realizando.
  39.        uint64_t iterator = number;  // Iterador de numeros primos.
  40.        /* Si el iterador es par lo disminuimos en una unidad, porque un numero
  41.          * par nunca va a ser primo y así ganamos eficiencia.
  42.          */
  43.  
  44.        if(iterator%2 == 0)
  45.                    --iterator;
  46.        while(sum != number)
  47.        {
  48.            if(isPrime(iterator))
  49.            {
  50.                sum += iterator;
  51.                printf(" %llu", iterator);
  52.                iterator = number - sum;
  53.                if(iterator%2 == 0)
  54.                    --iterator;
  55.            }
  56.            /* Decrementamos iterator en dos porque un numero par no es primo y
  57.              * por tanto no nos interesa.
  58.              */
  59.            else
  60.                iterator -= 2;
  61.        }
  62.    }
  63. }
  64. int  isPrime    (uint64_t number)
  65. {
  66.    // El uno es primo.
  67.    if(number == 1)
  68.        return 1;
  69.    // El dos es primo.
  70.    if(number == 2)
  71.        return 1;
  72.    // Todos los numeros pares no son primos.
  73.    if(number % 2 == 0)
  74.        return 0;
  75.    uint64_t sqr = (uint64_t) sqrt(number);
  76.  
  77.    /*  Si el numero que da la raiz es par, lo decrementamos en una unidad pues
  78.      *  solo nos interesan los numeros impares, ya que un numero impar no es di
  79.      *  visible por un numero par.
  80.      */
  81.    if(sqr % 2 == 0)
  82.        --sqr;
  83.  
  84.    while (sqr > 1)
  85.    {
  86.        if( number % sqr == 0)
  87.            return 0;
  88.        sqr -= 2;
  89.    }
  90.    return 1;
  91. }
« Última modificación: 9 Noviembre 2014, 01:43 am por avesudra » En línea

Regístrate en
crack81

Desconectado Desconectado

Mensajes: 222



Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #8 en: 8 Noviembre 2014, 20:51 pm »

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
En línea

Si C/C++ es el padre de los lenguajes entonces ASM es dios.
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Por favor ayuda con un programa en C, números primos
« Respuesta #9 en: 9 Noviembre 2014, 16:24 pm »

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
  1. Ingrese un valor :
  2. 10000000
  3. 9999991 7 2
  4. 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
  1. void SumaDePrimos ( int num ) {
  2.  int i , i2 , j , num1 , flag = 0 ,cont = 0 , suma = 0 ;
  3.  num1 = ( num % 2 == 0 ) ? num - 1 : num ; /* TOMO EL IMPAR SI NO LO ES */
  4.  for( i = num1 ; i >= -2 ;  i -= 2 ) { /* VOY DE DOS EN DOS Y EVITO LA OPERACION % */
  5.    if ( i == 1 )  i = 2 ;   /* ¡¡¡¡¡¡ */
  6.    if ( i == - 2 )  i = 1 ; /* ¡¡¡¡¡¡ */
  7.    i2 = i * i ; /* EVITO LA OPERACION SQRT */
  8.    for ( j = 1 ; j <= i2 ; j += 2 ) {
  9.      if ( i % j == 0 ) {
  10.         cont++ ;
  11.         if ( cont == 3 ) /* SI OCURRE NO ES PRIMO Y CORTO EL BUCLE */
  12.           break ;
  13.       }
  14.    }
  15.    if ( cont == 2 || cont == 1 ) {
  16.      suma += i ;
  17.      if ( suma < num )
  18.        printf ("%d " , i ) ;
  19.      else if ( suma == num ) {
  20.        printf ("%d " , i ) ;
  21.        break;
  22.      }
  23.      else if ( suma > num )
  24.        suma -= i ;
  25.      if ( flag == 0 ) /* TOMO EL IMPAR SI NO LO ES */
  26.        i = num1 - i + 1 , flag = 1 ;
  27.    }
  28.    cont=0;
  29.  }
  30. }

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


« Última modificación: 9 Noviembre 2014, 17:35 pm por leosansan » En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines