Prime Number Algorithm

Question

Qualcuno può dirmi come implementare l'algoritmo Sieve of Eratosthenes in C? Ho bisogno di generare numeri primi ma il mio algoritmo è lento.

Il mio codice:

#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 è il numero di casi di test M e N è l'intervallo tra i quali il primo sono da stampare.

Answer 1

È necessario creare una serie di valori booleani grandi quanto il numero primo massimo che si desidera trovare. All'inizio è completamente inizializzato a vero.

La cella i di tale matrice sarà vera se i è un numero primo o falso se non lo è.

Avviare iterando da i=2: è primo, quindi impostare su false qualsiasi cella con un indice multiplo di 2. Passare al numero primo successivo (i=3) e fare lo stesso. Vai al primo numero successivo (è i=5: i=4 non è primo: array[4] è stato impostato su false durante l'elaborazione di i=2) e fare lo stesso ancora e ancora.

Answer 2

Il collegamento di Marc B mostra un algoritmo semplice e corretto, corretto da NSLogan. Ho scritto una leggera modifica per mostrare alcuni compromessi di dimensioni/velocità. Pensavo di condividere per interesse.

In primo luogo, il codice:

#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; 
} 

(perdonate il messaggio di errore per non essere precisi quando USE_BITS è definito ...)

Ho confrontato tre diversi modi di memorizzare le variabili booleane che suggerito da Peoro. Un metodo utilizza effettivamente bit, il secondo richiede un intero byte e l'ultimo utilizza un'intera parola macchina. Un'ingenua ipotesi su quale sia il più veloce potrebbe essere il metodo della parola macchina, dal momento che ogni flag/booleano viene trattato in modo più "naturale" dalla tua macchina. I tempi per calcolare i numeri primi fino a 100 milioni sulla mia macchina è stata la seguente:

Bits: 3.8s Chars: 5.8S M-parole: 10.8s

E 'interessante notare che anche tutto il brutto lo spostamento di bit necessario per rappresentare un booleano con un solo bit è ancora più veloce nel complesso. La mia congettura è che il caching e la località di riferimento sembrano superare le istruzioni extra ~ 3. Inoltre, si finisce usando 1/nth della memoria del metodo n-bit-machine-word!

Answer 3

A mio parere, l'algoritmo rallenta perché si calcola il numero inessenziale. provare questo codice

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

Anche se è molto vecchio post, seguito è il mio tentativo di generare il numero primo con "Crivello di Eratostene" 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]); 
    } 
    } 

} 

Spero che questo aiuti qualcuno.

Answer 5

Qui è in realtà un codice molto semplice che utilizza l'algoritmo Sieve di Eratostene. funziona per tutti positivo int.

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