Come calcolare numeri primi partendo già da un valore noto?
Supponiamo questa situazione: sono già stati calcolati N numeri primi, ad esempio i primi 100.000 numeri primi, quindi con un determinato tempo di esecuzione. Ricordiamo ad esempio che f(105)=1.299.709.
Se volessi calcolare la lista fino al 300.000 numero primo, o meglio, vorrei conoscere il numero primo 300.000° in lista, sarebbe uno spreco di tempo e risorse calcolarli nuovamente tutti da zero! Quindi si può procedere in questo modo:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int main(){
register unsigned int cont=1;
register unsigned int MAXITER=200002;
register long int j=1299709;
register long int i=2;
register long int k;
long int V[MAXITER];
V[0]=1299709;
clock_t start = clock();
//creazione array di numeri primi
while(cont<MAXITER){
for(i=2;i<(int)(pow(j,0.5));i++){
if(j%i==0){break;}
}
if(j%i!=0){V[cont]=j;cont++;}
j++;
}
clock_t end = clock();
printf("%f s\n",(float)(end-start)/CLOCKS_PER_SEC);
printf("MAXITER=%d\nV[end]=%ld\n",MAXITER,V[MAXITER-1]);
return 0;
}
Vediamo meglio il codice:
- MAXITER 200002, significa 200.000 oltre il valore di partenza (100.000 in questo caso), +2 che aggiunto qui (infatti nel codice originale l'avevamo aggiunto a j che partiva da 3 anziché da 1, questa scelta insomma è arbitraria, una convenzione che per comodità ho scelto così)
- j=1299709 ovvero il valore noto di partenza: il numero primo numero 105 è pari a questo valore
- V[0]=1299709 ha senso scriverlo se poi ci interessa tutta la lista, se invece ci interessa solo la stampa a video del valore finale, questo non occorre
NB: ovviamente attenzione poi agli indici! Ad esempio V[0] si intende che lo zero sarebbe il numero di partenza, quindi ad esempio non zero bensì 100.000! Così come la funzione printf() che stampa a video i risultati, non l'ho corretta con gli indici aggiornati, insomma occorre saperlo! Se siamo partiti da zero fino a 105, l'ultimo valore dell'indice sarà 100.000-1, se invece siamo partiti da 100.000 fino a 300.000, sarà come detto prima nel punto relativo a MAXITER. Noi ovviamente sappiamo cosa stiamo calcolando quindi correggere gli indici non è indispensabile.
Risultati: eh sì, riportiamo la parte interessante, mica abbiamo fatto girare il codice per niente! 😃
- 300.000° numero primo = 4.256.233
- tempo di esecuzione del codice (partendo da 100.000): 17,9 secondi
E per quanto riguarda il milionesimo numero primo?
Ebbene, poi mi è venuta questa curiosità. Con un tempo di esecuzione pari a 115,6 secondi (partendo dal numero primo 300.000° in lista, calcolato prima), modificando il codice scritto prima ho voluto calcolare il milionesimo numero primo, dato che online non riesco a trovare scritto il suo valore. Ebbene, ve lo dico io: il milionesimo numero primo è 15485863.
