Algoritmo de número principal

Question

¿Alguien puede decirme cómo implementar el algoritmo Sieve of Eratosthenes en C? Necesito generar números primos, pero mi algoritmo es lento.

Mi código:

#include <stdio.h> 

int prime(long int i) 
{ 
    long int j; 
    int state = 1; 
    for(j=2;j<i;j++) 
    { 
     if((i%j)==0){state=0;break;} 
    } 
    return state; 
} 

int main() 
{ 
    int t; 
    long int m,n,i; 
    scanf("%d", &t); 
    while(t--) { 
     scanf("%d %d", &m,&n); 
     for(i=m;i<=n;i++) 
     { 
      if(i==1){ 
       //do nothing for 1 
      } else{ 
       if(prime(i))printf("%d\n",i); 
      } 
     } 
    } 
    return 0; 
} 

t es el número de casos de prueba m y n es el rango entre los que prime son para ser impreso.

Answer 1

Necesita crear una matriz de booleanos tan grande como el número primo máximo que desea encontrar. Al principio está completamente inicializado en verdadero.

La celda i th de dicha matriz será verdadera si i es un número primo, o falso si no lo es.

Comience a iterar desde i=2: es primo, luego establezca en falso cualquier celda con un índice múltiple de 2. Vaya al siguiente número primo (i=3) y haga lo mismo. Ir al siguiente primo (es i=5: i=4 no es primordial: array[4] se configuró en falso al procesar i=2) y hacer lo mismo una y otra vez.

Answer 2

El enlace de Marc B muestra un algoritmo simple y correcto, escrito por NSLogan. Escribí una pequeña modificación para mostrar algunos intercambios de tamaño/velocidad. Pensé que lo compartiría por interés.

En primer lugar, el código:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <assert.h> 
#include <time.h> 

#define USE_BITS 

#ifdef USE_BITS 
#define alloc_prime char *prime = calloc(i/8,sizeof(*prime)); 
#define set_not_prime(x) prime[x/8]|= (1<<(x%8)) 
#define is_prime(x) (!(prime[x/8]&(1<<(x%8)))) 
#endif 

#ifdef USE_CHAR 
#define alloc_prime char *prime = calloc(i,sizeof(*prime)); 
#define set_not_prime(x) prime[x] = 1 
#define is_prime(x) (prime[x] == 0) 
#endif 

#ifdef USE_SIZE_TYPE 
#define alloc_prime size_t *prime = calloc(i,sizeof(*prime)); 
#define set_not_prime(x) prime[x] = 1 
#define is_prime(x) (prime[x] == 0) 
#endif 


int main(){ 
    int i; 
    printf("Find primes up to: "); 
    scanf("%i",&i); 

    clock_t start, stop; 
    double t = 0.0; 

    assert((start = clock())!=-1); 

    //create prime list 
    alloc_prime; 
    int c1, c2, c3; 
    if(!prime){ 
    printf("Can't allocate %zu bytes!\n",i*sizeof(*prime)); 
    exit(1); 
    } 

    //set 0 and 1 as not prime 
    set_not_prime(0); 
    set_not_prime(1); 

    //find primes then eliminate their multiples (0 = prime, 1 = composite) 
    for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){ 
    if(is_prime(c2)){ 
     c1=c2; 
     for(c3 = 2*c1;c3 <= i+1; c3 += c1){ 
     set_not_prime(c3); 
     } 
    } 
    } 

    stop = clock(); 
    t = (double) (stop-start)/CLOCKS_PER_SEC; 

    //print primes 
    for(c1 = 0; c1 < i+1; c1++){ 
     if(is_prime(c1))printf("%i\n",c1); 
     //  if(prime[c1] == 0) printf("%i\n",c1); 
    } 
    printf("Run time: %f\n", t); //print time to find primes 

    return 0; 
} 

(Perdona el mensaje de error por no ser precisa cuando se define USE_BITS ...)

He comparado tres maneras diferentes de almacenar las variables booleanas que sugirió Peoro. Un método realmente usa bits, el segundo toma un byte completo, y el último usa una palabra de máquina completa. Una suposición ingenua sobre cuál es la más rápida podría ser el método de palabras de la máquina, ya que cada marcador/booleano es tratado con más 'naturalidad' por su máquina. Los horarios para el cálculo de los números primos hasta 100 millones en mi máquina fueron los siguientes:

Bits: 3.8s Caracteres: 5.8S M-palabras: 10.8s

Es interesante notar que incluso todo lo feo el cambio de bit necesario para representar un booleano con solo un bit es aún más rápido en general. Mi conjetura es que el almacenamiento en caché y la localidad de referencia parecen superar las ~ instrucciones adicionales. ¡Además, terminas usando 1/nth la memoria del método n-bit-machine-word!

Answer 3

En mi opinión, su algoritmo se ralentiza porque calcula el número inesencial. probar este código

int isPrime(int number){ 

    if(number < 2) return 0; 
    if(number == 2) return 1; 
    if(number % 2 == 0) return 0; 
    for(int i=3; (i*i)<=number; i+=2){ 
     if(number % i == 0) return 0; 
    } 
    return 1; 

} 

Answer 4

Aunque es muy antiguo puesto, que sigue es mi oportunidad para generar el número primo usando "criba de Eratóstenes" algoritmo.

#include <stdio.h> 

#define NUM 8000  /* Prime Numbers in the Range. 'Range + 2' actually. */ 

int main() 
{ 
    int a[NUM] = {0};   /* Array which is going to hold all the numbers */ 
    int i , j; 

    /* initializing array from 2 to given number + 2, assuming the first prime number is 2 */ 
    for(i = 2,j=0; i < NUM+2, j<NUM; i++, j++) 
    { 
    a[j] =i; 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    int num = a[i]; 

    /* If number is not 0 then only update the later array index. */ 
    if(num != 0) 
    { 
     for (j = i+1; j < NUM; j++) 
     { 
     if((a[j]%num == 0)) 
     { 
      a[j]=0; 
     } 
     } 
    } 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    /* Print all the non Zero *Prime numbers* */ 
    if(a[i] != 0) 
    { 
     printf("%d \n", a[i]); 
    } 
    } 

} 

Espero que esto ayude a alguien.

Answer 5

Aquí hay un código muy simple que usa el algoritmo Sieve of Eratosthenes. funciona para todos los positivos int.

int is_prime(int n){ 
    int p; 
    for(p = 2; p < n; p++){ 
    if(n % p ==0 && p != n) 
     return 0;  
    } 
    return 1; 
}