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/Algoritmi_per_la_generazione_dei_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è :sneer:

[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? :hm:


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! :metal:

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 :sneer:
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 :sneer:
comunque pensavo fosse per uni o simile, se hai bisogno i numeri, ci sono le liste...

18.446.744.073.709.551.615 è minuscolo :D
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 :sneer:

[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 :D

[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 :D

[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 :D
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?

[Amiag]

imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono

[Brcondor]

imo questa è una di quelle cose per cui non dovresti mai inventarti algoritmi ma usare quelli che ci sono
quali?

[Amiag]

http://it.wikipedia.org/wiki/Crivello_di_Eratostene

o per roba piu complessa

http://www.dti.unimi.it/citrini/MD/SitoG-M/algoritmi.htm


30 secondi

[Eltarion]

tra l'altro potresti usare la programmazione dinamica per salvare i risulatati parziali e non rifare gli stessi calcoli. se riesci a ridurre il numero dei calcoli fai come una scheggia!

[Brcondor]

Dato che sapere se il numero è primo è solo il primo step e quello che vorrei creare è ua omna sorta di programmino dinamico e aggiornabile la soluzione che mi consigli l'ho già implementata. Ho considerato un caso base(lancio il programma su un pc nuovo) in cui passo i primi 5 numeri primi, cosa che mi serve per andare a regime. Tutte le chiamate successive mandando anche il vettore dei evcchi numeri primi e eventualmente qualora per fare il test ne scopro altri riaggiorno il tutto. Quindi la problematica computazionale non è piu assoluta ma relativa. ORa mi leggo il tuo link. Il crivello di eratostene nn è utile per cercare numeri primi grandi. Ci sono altri metodi che mi sto studiando e sto cercando di capire... qualcuno mi spiega perchè miller rabin funziona in parole povere?

[Brcondor]

mi dite se ho capito giusto?
Prendo n da testare.Faccio n-1. Lo divido tante volte finche n-1/2 non da resto. Alche trovo una scomposizione del tipo
n-1=2^s * d
Scelgo un a primo a caso, scelgo per semplicità 2
a^d (modn)== 2^d modn = 1 il numero non è sicuramtne primo
!=1 il numero potrebbe essere primo
Giusto?

[dariuz]

scegli i numeri fino a N, prendi un n e cominci a dividerlo per tutti gli interi compresi fra 2 e RADQ(N) e calcoli il resto, se il resto è sempre diverso da 0 hai un numero primo.
è la versione da bambini :nod:

altrimenti questo dovrebbe essere una specie di quello attualmente in uso (un elaborazione del test di fermat)

http://en.wikipedia.org/wiki/AKS_primality_test