Problema simple con programa números primos

[jamatbar]

Buenas, aquí estoy empezando con C++ y tengo una duda con un ejercicio de una práctica de la facultad.

Tengo un programa (muy rudimentario) que tengo que ir mejorando poco a poco, el programa me dice si un número no es primo y si sí es primo sale del programa, este es el código:

Código [Seleccionar] Expandir

#include <stdio.h>

#define RESPUESTANOPRIMO " %d no es primo\n"
#define RESPUESTAPRIMO   " %d es primo\n"

int main()
{
  /* Almacenara el numero leido por teclado */
  int valor;
  /* Servira como indice del bucle for que vamos a utilizar. */
  int i;
  /* Solicitamos el numero que queremos saber si es primo */
     printf("Introduzca un valor: ");
     scanf(" %d", &valor);
     
/* El bucle lo comenzamos en 2: todo numero es divisible por 1
* y lo terminamos antes de valor: todo numero es divisible por si mismo */

for ( i = 2; i < valor; i++ )
     if (0 == (valor % i))
     /* Si el resto es cero, es porque i divide
     * No es primo. */
     printf(RESPUESTANOPRIMO, valor);

  return 0;
}

Y me pide que una vez comprobado que el dos no es divisor, probar sólo con los números impares.

Yo creo que debo cambiar ese i++ por un i+=2, para que desde el 3 todas las demás comprobaciones se hagan con números impares, pero no sé como inicializar la variable i en el 3 después de la primera "pasada" del bucle for. Lo que he hecho es esto:

Código [Seleccionar] Expandir

#include <stdio.h>


#define RESPUESTANOPRIMO    "%d no es primo\n"
#define RESPUESTAPRIMO      "%d es primo\n"



int main()
{
  /* Almacenara el numero leido por teclado */
  int valor;
  /* Servira como indice del bucle for que vamos a utilizar. */
  int i;

  /* Solicitamos el numero que queremos saber si es primo */
  printf("Introduzca un valor: ");
  scanf("%d", &valor);

  if (valor == 2);

  else

    {
      if (0 == (valor % 2))


/* Si el resto es cero, es porque i divide  a numero:
* No es primo. */
        printf(RESPUESTANOPRIMO, valor);
      else
        {
          for (i = 3; i < valor; i += 2)
            if (0 == (valor % i))
              /* Si el resto es cero, es porque i divide a numero:
               * No es primo. */
              printf(RESPUESTANOPRIMO, valor);
        }

    }

  return 0;
}

Que hace lo que quiero pero no creo que deba sacar el 2 "a lo bruto" del bucle for, ¿alguna ayuda?

No hace falta mejorar el programa, sólo hacer dicha modificación para luego poder hacer otros apartados que me piden.

Gracias de antemano y un saludo!

[engel lex]

normalmente por la inconveniencia que presenta el 2 como par-primo si se saca del bucle, recomiendo el i nada más recorrerlo hasta la raíz del numero ingresado, ya que más allá de la raíz estarías repitiendo divisores ya que ese es el factor donde pivotan los valores

ej

Código [Seleccionar] Expandir

210 (raíz ~14.5)
=1*210
=2*105
=3*70
=5*42
=6*35
=7*30
=10*21
=14*15 (aquí está el pivote, a partir de aqui serán las mismas cuentas invertidas)
=15*14
=21*10
...(etc)

entonces ejemplo, para saber si 211 (raíz ~14.5) es primo solo basta con probar 2, 3, 5, 7, 9, 11, 13 según tu algorimo y solo probarías 7 factores en lugar de 211 dandole mucha velocidad...

y por lo menos 3.123.133 en lugar de probar más de 1millon de factores, solo pruebas unos 884 factores y listo...

[Blaster]

Otra forma de reducir exponencialmente el número de iteraciónes es la siguiente:

Código (cpp) [Seleccionar] Expandir

for (i = 3; i * i <= valor; i += 2)

Saludos   

[engel lex]

Otra forma de reducir exponencialmente el número de iteraciónes es la siguiente:

Código (cpp) [Seleccionar] Expandir

for (i = 3; i * i <= valor; i += 2)

Saludos   

justamente lo que explicaba, aunque siempre olvido para la raíz usar este método!

[leosansan]

entonces ejemplo, para saber si 211 (raíz ~14.5) es primo solo basta con probar 2, 3, 5, 7, 9, 11, 13 según tu algoritmo y solo probarías 7 factores en lugar de 211 dándole mucha velocidad...

y por lo menos 3.123.133 en lugar de probar más de 1 millón de factores, solo pruebas unos 884 factores y listo...

Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=999 (1000).

Pero aún así se estaría trabajando en balde ya que probaríamos, entre otros, 15, 25, 27, 33, 35, 45, 49, ......que sería una redundancia ya que si  es divisible entre 3 y 5 el probar con 15 está de más y así sucesivamente.

Es decir, tan sólo hay que probar con divisores que, además de ser impares, sean primos, es decir:

3 , 5 , 7, 11 , 13 , 15 , 17 , 19 , 21 , 23 , 25 , 27  , 29 ,31 ,   33  ,   35 , 37 , 39 , 41 , 43 , 45 , 47 ,   49 ......

En el caso de 1000 000 hasta num = 1000 ( 1000*1000=1000000) hay en principio que tomar los impares, que son 500. Pero de ellos tan sólo hay 168 primos con lo que ya reducimos considerablemente el número de probaturas.

Y en el caso de 100 000 0000 hay ¡¡¡ "50 000 000" ¡¡¡ de impares pero tan solo 5 761 455 primos, con lo que ahorramos las pruebas en un factor de casi 20.

Por lo que de una forma simple se pueden ir guardando los primos obtenidos en un array, "primos", e ir probando sólo a estos en lugar de todos los impares, algo como:

Código (cpp) [Seleccionar] Expandir

 for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ) {
     if ( n % primos[k] == 0 )

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

[engel lex]

Eso último no está nada claro, si el número es 1 millón habría que probar según tu propuesta hasta num*num = 1000 000 , es decir de 3 a num=1000.

no entendí lo que no estaba claro D: pero extiendo

en lugar de probar de 2 en 2 desde 3 hasta 3.123.133 (dando unos 1,5millones de ciclos) se haría desde 3 durante i*i <= 3.123.133 siendo unos 884 ciclos si no me equivoco...

lo que tu dices de saltar todos los otros factores no me parece una buena idea, porque implicaría almacenar en memoria todos los factores intermedios y evaluarlos creando un ciclo secundario... siento que se haría un motón de operaciones de modulo extra en lugar de simplemente el modulo del numero que si falla es uno solo y listo...

o por lo menos que entendí de tí sería algo como esto...

Código (cpp) [Seleccionar] Expandir


for (i = 3; i * i <= valor; i += 2){
    for ( primos[k] ; prims[k] * primos[k] <= n ; k++ ){
        if ( n % primos[k] == 0 ) //ir con el siguiente i
    }
    //si no saltó almacenar i en arreglo



-----sigo agregando-----

la cantidad original de modulos a ejecutar era
n/2-3

yo lo indico llevar a
sqrt(n)/2-3

tu lo estás llevando a
(n-3)*k!
donde k es la cantidad de primos intermedios :s (ya que serían 2 ciclos haciendo mods y el segundo creciendo en cada vuelta de n)

incluso pensé hace tiempo que podría hacerse

Código (cpp) [Seleccionar] Expandir


for (i = 3; i * i <= valor; i += 2){
    if(i%3==0) continue;
    if(i%5==0) continue;

porque "aumenta" la eficiencia en ~20% pero no, ya que al final en el mejor de los casos hace 1 mod (si es multiplo de 3), y en el peor hace 3 mods, sabiendo que en este ciclo la operacion más pesada es el mod y es igual en tiempo para %3 y  %3.000.000, entonces no vale la pena el procesamiento extra

[ivancea96]

El problema de guardar un array de primos, es para números mayores a un millardo. Ahí podría empezar a consumir hasta un GB de memoria.

[leosansan]

no entendí lo que no estaba claro D: pero extiendo
.............................................................

Está claro que no me exprese bien, sorry!!!.

Yo no hablaba del caso de comprobar si "un" número concreto es o no primo sino de calcular  los números primos en un intervalo, como de 1  10^8, por ejemplo. Está claro que si sólo es un número es casi impepinable usar el método del módulo, y aún así se pueden introducir mejoras.

En cuanto al número de operaciones es al menos menor ya que lo único que se hace es sustituir la operación de "i*i<N" por "primos[ i ]*primos[ i ]<N". El motivo de que sea menor es que en el método del "i*i" se usan todos los impares desde 3 a la raíz del número en el peor de los casos, como en el caso de querer comprobar si 99991 es o no primo, sin embargo en el método del array sólo se usan los primos previamente  calculados que obviamente son menores que los impares. La única penalización es el uso de un array y que tampoco ya que lo que procede realmente es ir guardando los primos calculados en en fichero y escribir y leer los cuando proceda. Como ves, se consigue disminuir el número de operaciones módulo en unos cuantos miles, todo lo cual redunda en una mejora, al menos sobre el papel.

No obstante, y para que no digan que hago tareas, será en este otro hilo, cortesía de ivancea96 aporte_detector_de_numeros_primos_en_c donde podrás encontrar una comparativa de los métodos y donde se pone de manifiesto la bondad del método del uso de "primos" frente al "i*i"

Espero que ahora esté más claro.



Un fuerte saludo de León amigo engel lex.

[engel lex]

Está claro que no me exprese bien, sorry!!!.

Yo no hablaba del caso de comprobar si "un" número concreto es o no primo sino de calcular  los números primos en un intervalo, como de 1  10^8, por ejemplo. Está claro que si sólo es un número es casi impepinable usar el método del módulo, y aún así se pueden introducir mejoras.

En cuanto al número de operaciones es al menos menor ya que lo único que se hace es sustituir la operación de "i*i<N" por "primos[ i ]*primos[ i ]<N". El motivo de que sea menor es que en el método del "i*i" se usan todos los impares desde 3 a la raíz del número en el peor de los casos, como en el caso de querer comprobar si 99991 es o no primo, sin embargo en el método del array sólo se usan los primos previamente  calculados que obviamente son menores que los impares. La única penalización es el uso de un array y que tampoco ya que lo que procede realmente es ir guardando los primos calculados en en fichero y escribir y leer los cuando proceda. Como ves, se consigue disminuir el número de operaciones módulo en unos cuantos miles, todo lo cual redunda en una mejora, al menos sobre el papel.

No obstante, y para que no digan que hago tareas, será en este otro hilo, cortesía de ivancea96 aporte_detector_de_numeros_primos_en_c donde podrás encontrar una comparativa de los métodos y donde se pone de manifiesto la bondad del método del uso de "primos" frente al "i*i"

Espero que ahora esté más claro.



Un fuerte saludo de León amigo engel lex.

ahora si te comprendí en ese ejemplo si es muy bien aplicable la idea!

[leosansan]

ahora si te comprendí en ese ejemplo si es muy bien aplicable la idea!

Siento no haberme explicado con claridad la primera vez. Gracias por la comprensión.

Un fuerte saludo de León.