/********************************************************* * CRIVELLO DI ERATOSTENE (velocizzato) * input: L - limite entro il quale ricercare i primi. * output: vettore contenente tutti i primi tra 2 e L. * * Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli. * Capitolo 6.3 pag. 165-166 *********************************************************/ {Eratsmart(L) = local(a, l, i, l1, u, j, npi, k, primi, primiout); /* inizializziamo un vettore di L componenti * booleane. In Gp Non e' possibile farlo * direttamente. Allora poniamo a uguale al * numero che ha L cifre binarie uguali a 1 */ a=binary(2^L-1); l=length(a); /* intendiamo come marcato un intero j la cui * corrispondente componente di a e' zero. * La componente a[j] viene posta uguale * a zero se l'intero j e' un multiplo di uno * degli interi precedenti. */ i = 2; l1= floor(sqrt(l)); while(i <= l1, /* "saltiamo" gli interi gia' marcati */ while(a[i] == 0,i = i + 1); /* alla fine del while, a[i]=1 indica * che i deve essere un primo perche' * non e' diviso da nessun intero piu' * piccolo. * Marchiamo adesso i multipli dell'intero * i ossia azzeriamo le componenti di a * corrispondenti agli interi * j*i, per j che varia fino a [l/i]. */ u= l \ i; for(j=i, u , a[i*j] = 0); /* passiamo ora a studiare la primalita' * dell'intero successivo incrementando la * variabile che governa il while piu' esterno */ i=i+1; ); /* restituiamo in output il vettore i primi */ primi=vector(l); npi=1; for (k=2,l, if ((a[k]<>0), primi[npi]=k;npi=npi+1)); /* Sappiamo anche quanti sono i primi minori o uguali * a L (sono npi-1) */ print("Il numero di primi minori o uguali a ", L, " e': ", npi-1); primiout=vector(npi-1); for(k=1,npi-1,primiout[k]=primi[k]); print("I numeri primi minori o uguali a ", L, " sono dati dal vettore: "); return(primiout); /******** OUTPUT PIU'LENTO *npi=1; *print1 (2); *for (j=3,l, * if ((a[j]<>0), print1(" , ", j) ;npi=npi+1)); *print("."); ************/ }