Buscando números primos, con la criba de Eratóstenes

[leosansan]

Iniciado por CalgaryCorpus

...............................
Este par de multiplicaciones se puede reemplazar por 1 suma, debido a que el ciclo lo que hace es calcular los factores del numero i, es decir calcula 2*i, 3*i, 4*i, ... ( y asi sucesivamente ) y ese valor utiliza.

En vez de multiplicar todas las veces, se puede guardar el valor anterior y descubrir el siguiente sólo sumando i, asi (ver variable "multiplo"):
...............................

Bien observado lo de la multiplicaciónCalgaryCorpus, ya lo he puesto en práctica.

Y lo de inicializar fue un fallo de pasar un código previo, pero también bien observado.

Lo dejo con calloc para además de declarar, inicializar y con N de 10^8 con lo que tarda unos 7 segundos en mostrar el total de primos. Desactivo los printf para que "no pierda tiempo" en calcular el total de primos hasta N:

Código C++:

#include <stdio.h>
#include <stdlib.h>
#define N 100000000 /* hasta aqui calculamos los primos */
 
int main() {
  int i, j, z, x = 0;
  int  *nums = calloc( N+1, sizeof ( int ));
  int *prims = calloc( N+1, sizeof ( int ));
  ///puts("\n\tSon PRIMOS:\n");
  ///printf( "\t%4d:::%5d\n", x, 2 );
  prims[x] = 2;
  x++;
  for( i = 3; i <= N; i += 2 )
    if( nums[i] == 0 ) {
      prims[x] = i;
      ///printf( "\t%4d:::%5d\n", x, i );
      x++;
      for( j = ( i <= N ); ( z = ( i * j ) )  <= N; j+=2)
        nums[z] = 1;
    }
  /*for( i = 0; i < x; i ++ )
    printf( "%4d", prims[i] );*/
  printf( "\n  Hasta %d hay %d numeros primos\n\n", N, x );
  free ( nums );
  free ( prims );
  return 0;
}
}
 

EDITADO:

Mirándolo bien amigo CalgaryCorpus acabo de darme cuenta de un par de detalles. En tu for vas de multiplo = i+i con incrementos de multiplo += i.

Como ejemplo, supongamos para i los valores de 3 y de 5. Aplicándoles el for los valores que tomarían serían de:

3+3=6______5+5=10
+3=9-_____+5=15
+3=12_____+5=20
+3=15_____+5=25
+3=18_____+5=30
.....................

donde se observa que toman de forma inútil valores pares, que de antemano sabemos que no son primos y arrancan siempre con valor par al ser i+i. La forma de evitarlo sería con un paso de 2*i y un valor inicial de 3*i .

Y como ves tu intento de mejora para evitar la multiplicación de i * j se traduce en la introducción de nuevas multiplicaciones. Claro que al ser una de ellas de multiplicar por dos se podría optimizar más fácilmente.

En cualquier caso es de agradecer y motiva que haya gente por ahí que se moleste en mirar con tanto detenimiento los códigos. Gracias por la atención que le has prestado.

Un fuerte saludo.