lista di primi

[primonumero]

A chi interessa ho sviluppato due function per generare una lista di numeri primi in linguaggio PARI/GP (http://pari.math.u-bordeaux.fr/) (occorre infatti una certa potenza di calcolo). La lista è limitata a 50 elementi ma nel ciclo for si può cambiare questo numero a piacere. Io l'ho provata e funziona bene. Il gcd è il Massimo Comun Divisore, il "!" è il fattoriale, ecc
------------------------------------------
versione 1)
{tabella() = local(p, i);
p = 3;
p = p+2;
for(i=1, 50,
if(gcd(p, floor(sqrt(p))!) == 1, print(p));
p = p+2);
return(1);}
-----------------------------------
versione2)
{tabella2() = local(p, i, k);
k = 3;
k = k+2;
p = 3;
for(i=1, 50,
if(gcd(p, k) == 1, print(k), p = p*k);
k = k+2);
return(1);}

[primonumero]

questa versione è invece in JAVA usando le librerie BigInteger e BigDecimal

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.*;
public class Main {

public static void main(String[] args) {
long j =1;
BigInteger inizio = new BigInteger("3");

BigInteger passo = new BigInteger("2");

inizio = inizio.add(passo);

System.out.println(inizio);
while(j < 1000000000){
if( inizio.isProbablePrime(100000000))

System.out.println(inizio);
inizio = inizio.add(passo);
j = j+1;
}


}

}

[Rggb]

Sono un po' lente, non credi?

[primonumero]

si è vero:
1) i programmi in PARI/GP necessitano di una certa potenza di calcolo anche se in linea teorica possono generare primi all'infinito (sono in raltà delle piccole varianti del crivello di Eratostene).
Ovviamente è possibile costruire una semplice subroutine che sfrutti con un cliclo for "prime(i)" ovvero la fuzione già impostata che dà l'i-esimo numero primo i. Con quest'ultima soluzione si può costruire la lista fino al 400.000° numero primo perché poi per andare oltre bisgona modificare le impostazioni del PARI/GP.

2) l'applicazione in JAVA mi sembra rapida però è ovvio che essendo i numeri primi infiniti ci vuole comunque un certo tempo per calcolare almeno un gruppo di 100.000 primi. L'applicazione altro non fa che sottoporre ad un test di primalità ogni nuemero dispari: se il numero supera il test lo stampa a video altrimenti no e si passa al numero dispari successivo. Per il test di primalità si usa la funzione "isprobableprime" che è compresa nel pacchetto BigInteger e che può essere utilizzata anche su numeri a molte cifre. Decidere se un numero è primo o no con un test di primalità è ovviamente molto più veloce che fattorizzarlo.

[primonumero]

comunque la spiegazione del metodo (quello che ho scirtto in codice PARI/GP) è descritta in http://www.box.net/shared/793vhag44f
Con l'applicativo in Java invece mettendo come valore iniziale un qualunque numero dispari anche grande a piacere posso generare velocemente numeri primi maggiori o uguali al valore iniziale (qui però il merito è della libreria BigInteger e della funzione isprobableprime()).