numeri primi

[Brcondor]

Qualcuno conosce qualche algoritmo intelligente per calcolare i primi n numeri primi?

[dariuz]

ci sono premi in $ astronomici per chi riesci a trovare i numeri primi (se non sbaglio siamo tipo al 42mo numero primo di Mersenne)

cmq Prime95 il software per benchmark se non sbaglio calcola numeri primi per sfruttare la cpu

se N è abbastanza contenuto qualcosa puoi fare http://it.wikipedia.org/wiki/Algorit...i_numeri_primi

cmq per moar info leggiti le robe sul GIMPS

[Axet]

Non esistono algoritmi per il calcolo dei numeri primi, esistono i test di primalità.
Dai un occhio all'algoritmo di Miller-Rabin.

Btw è utile se vuoi sapere se un dato numero è primo o no, per calcolarli tutti dovresti testarli tutti. Puoi escludere tutti i numeri pari e sicuramente esiste qualche altro modo più furbo per ridurre lo spazio di ricerca, ma in ogni caso rimane sempre un qualcosa di gigantesco.

edit:
Chiaro che se vuoi trovare tutti i numeri primi compresi tra 1 e 100 non c'è problema, non capisco a cosa ti possa servire ma vabbè

[Brcondor]

Si, ho pensato di escludere tutti i numeri che finiscono per 0 2 4 5 6 8.
Attualmente con tempi di calcolo umani(max 10 minuti) sn riuscito a calcolare senza fare impallare tutto i numeri primi tra i "primi 2.000.000" di numeri (149.000 numeri primi).
Già sapere se è primo o no potrebbe essere perfetto per i miei scopi, poi ci do un occhio. Thx mille, quando venderò i miei brevetti in tutto il mondo avrete laut compensi :P

[Hador]

esistono diversi modi per ridurre lo spazio di ricerca e diversi modi per farlo parallelamente. Google e passa la paura. A sentimento direi che è un esercizio...
10 minuti per 2000000 me pare tantino...

[Axet]

Si, ho pensato di escludere tutti i numeri che finiscono per 0 2 4 5 6 8.

lol?
Fare modulo 2 e vedere se il resto è 0 no eh?

Attualmente con tempi di calcolo umani(max 10 minuti) sn riuscito a calcolare senza fare impallare tutto i numeri primi tra i "primi 2.000.000" di numeri (149.000 numeri primi).
Già sapere se è primo o no potrebbe essere perfetto per i miei scopi, poi ci do un occhio. Thx mille, quando venderò i miei brevetti in tutto il mondo avrete laut compensi :P

No ma forse non hai capito, oltre un certo livello manco coi supercomputer ci arrivi. 2.000.000 è un numero ridicolo, quando ho implementato RSA testavo la primalità su numeri di ALMENO 150 cifre.
Cmq son curioso di sapere a cosa ti serve ^^,

esistono diversi modi per ridurre lo spazio di ricerca e diversi modi per farlo parallelamente. Google e passa la paura. A sentimento direi che è un esercizio...
10 minuti per 2000000 me pare tantino...

Si ma anche se riduci lo spazio di ricerca non vai un po' da nessuna parte, idem andando parallelamente. Magari invece di metterci 4 miliardi di anni ce ne metti 2, yay!

edit:
dimenticavo, stai ben attento che miller-rabin (ma direi con ragionevole certezza tutti gli algoritmi per il test di primalità un pelo efficienti) è probabilistico.. non ti basta eseguirlo una volta per ogni numero che testi.

[Brcondor]

Boh, poi provo a cronometrare. Ma verificare se 2.000.000 di numeri sono primi o meno richiede un bel po' di tempo credo.
In maniera standard(mettendosi a testa bassa senza ragionare) per ogni i-esimo numero devo verificare che non sia multiplo di tutti gli i-1 numeri che lo precedono: sono un fottio di operazioni... anche perchè andando su con le cifre i conti diventano sempre piu computazionalmente onerosi. 7/2 + 7/3 + 7/5 != 2.000.003 / 2 + 2.000.003 /3 + .... + 2.000.003 /2000002

[Hador]

bhe considerando che arrivi fino a 18.446.744.073.709.551.615 e che han scoperto numeri primi ben più grandi, secondo me è fattibile
comunque pensavo fosse per uni o simile, se hai bisogno i numeri, ci sono le liste...

[Brcondor]

è per uni e per quel che serve a me non mi interessa neanche lontanamente superare il 10^12 come massimo numero da testare se è primo...
Cmq thx mille.
@ axet è un progetto per un corso, progetto che col corso non centra molto. Mi servirebbe implementare una serie di funzioni che vadano a mostrare alcune proprietà di alcuni particolari numeri naturali: alla base di tutto è che il numero sia primo. Non mi interessa sapere se un numero di ordine 30 è primo.

[Axet]

Boh, poi provo a cronometrare. Ma verificare se 2.000.000 di numeri sono primi o meno richiede un bel po' di tempo credo.
In maniera standard(mettendosi a testa bassa senza ragionare) per ogni i-esimo numero devo verificare che non sia multiplo di tutti gli i-1 numeri che lo precedono: sono un fottio di operazioni... anche perchè andando su con le cifre i conti diventano sempre piu computazionalmente onerosi. 7/2 + 7/3 + 7/5 != 2.000.003 / 2 + 2.000.003 /3 + .... + 2.000.003 /2000002

Buongiorno eh, come già detto esistono i test di primalità apposta. L'algoritmo naive che hai scritto è, appunto, naive.

bhe considerando che arrivi fino a 18.446.744.073.709.551.615 e che han scoperto numeri primi ben più grandi, secondo me è fattibile
comunque pensavo fosse per uni o simile, se hai bisogno i numeri, ci sono le liste...

18.446.744.073.709.551.615 è minuscolo
Come già detto per RSA servono numeri primi di almeno 150 cifre, e sebbene possano sembrare grandi sono in ogni caso una briciola.
Per capirci, riporto da wiki:
<<In 2009, the Great Internet Mersenne Prime Search project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits.[19] The Electronic Frontier Foundation also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.>>

10 milioni di cifre. Auguri brcondor

[Axet]

è per uni e per quel che serve a me non mi interessa neanche lontanamente superare il 10^12 come massimo numero da testare se è primo...
Cmq thx mille.
@ axet è un progetto per un corso, progetto che col corso non centra molto. Mi servirebbe implementare una serie di funzioni che vadano a mostrare alcune proprietà di alcuni particolari numeri naturali: alla base di tutto è che il numero sia primo. Non mi interessa sapere se un numero di ordine 30 è primo.

Vabbè 10^12 è isi.
Il metodo più semplice che mi viene in mente è: dividi facile facile lo spazio di ricerca in due (consideri solo i numeri dispari) senza farti altri calcoli strani che tanto per una cifra così bassa non ti servono, poi spari miller-rabin a raffica per ogni numero. Magari ci mette qualche ora ma ce la fa senza patemi

edit:
di nuovo un appunto sul fatto che MB è un test probabilistico.
La probabilità di errore per una singola applicazione è 1/4. Applicalo N volte (in maniera indipendente obv) e la probabilità di errore diventa 1/(4^N). Tanto più alto N tanto più sarai sicuro che il numero è primo.. tienilo il più alto che riesci considerando anche i tempi di calcolo

[San Vegeta]

aggiungo solo che al posto di "modulo 2", se fai uno shift a destra e ottieni 0, il numero è pari e quindi da escludere, operazione velocissima

[Dr.Doomed]

aggiungo solo che al posto di "modulo 2", se fai uno shift a destra e ottieni 0, il numero è pari e quindi da escludere, operazione velocissima

Giusto per fare la punta al cazzo, 2 e` un numero primo.
Ad ogni modo, se parte da 3 e itera calcolando il numero da verificare successivo aggiungendo 2, modulo 2 o rightshift se li puo` evitare del tutto, cosa piu` veloce in assoluto.

[Abby]

Se l'intervallo è da 1 al numero n, e se hai memoria il crivello di Eratostene è sufficientemente semplice e veloce (mi raccomando che non usi modulo ma elimini i multipli) complessità O(n(logn)(loglogn))

[Brcondor]

Per evitare questi problemi ho usato un trucchetto che funziona da dio.
Come vettore di numeri primi ne do uno fino a 11(1 2 3 5 7 11).
Per vedere se un numero maggiori di 11 è primo prendo una i che parte da 11+k e arriva fino a questo numero testando la primalità di ogni numero.
k varia: vale 2 se l'ultima cifra è 1,7,9 e vale 4 se l'ultima cifra del numero primo i-1 è 3. Cosi farei 11 - 13- 17 -19 -21-23-27-29 saltando cioè i multipli di 2 e 5 senza fare un conto.
Una volta che ho testato chessò 44 (che non è primo ma mi permette di allungare il vettore di numeri primi con 13 17 19 23 29 31 37 39 41 43) e voglio testare il 49 riparto da 43(quindi i=47 e poi i=49). Andando avanti per iterazioni successive posso scrivere enormi vettori di numeri primi minimizzando i conti. Avete qualche consiglio/idea/suggerimento?