numeri primi

[lunaxv]

ciao a tutti , vorrei chiedere una cosa..

Per sapere se un numero e' primo o no, quali "astuzie" ci sono? Il Brute-Force di provare tutti i numeri da 2 a N/2 e' brutto

Grazie a tutti

[fireball]

Un numero si definisce primo se è divisibile solo per 1 e per se stesso.
Un metodo per verificarlo è scomporre il numero in fattori primi; esempio: prendiamo il numero 35: esso è dato da 7*5 (che sono entrambi numeri primi); ora prendiamo il numero 37: questo è divisibile solo per se stesso e per uno e pertanto non è scomponibile. Conclusione: il numero 37 è primo.

In molti libri di testo delle scuole medie e superiori dovrebbero esserci delle tavole con tutti i numeri primi; ce ne è una anche in rete, molto ben fatta, che si trova al seguente indirizzo:

http://www.math.it/formulario/primi.htm

ciao
fireball

[lunaxv]

eh
il mio progetto e' scoprire un numero primo con almeno un miliardo di cifre cosi' netprime mi offre 300 mila dollari

ma nn per i soldi, e' cosi' una sfida

solo che devo fare un programmino che dovro distribuire alla gente per velocizzare il controllo di un numero..

Il numero verra dettato da 2^n-1 , con n molto grande..

Una volta che avro finito il programmino lo distribuiro' a chiunque lo voglia

[goblyn]

Io tifo x te!!! così mi dai una %... <img src=icon_smile_wink.gif border=0 align=middle><img src=icon_smile_big.gif border=0 align=middle>

[fireball]

Mi unisco al goblyn ...<img src=icon_smile_wink.gif border=0 align=middle><img src=icon_smile_tongue.gif border=0 align=middle>

[goblyn]

comunque in questa pagina in alto clicca su cerca e scrivi numeri primi (cerca frase esatta). Troverai un po' di post sul tema! ciao

[lunaxv]

hehehe grazie

cmq quando ho finito il programmino lo linko su un post cosi' chi vuole puo' tenerlo un po' acceso quando vuole <img src=icon_smile_big.gif border=0 align=middle>

[tony]

Mi pare che il brute-force possa essere arrestato a sqrt(n), invece che a n/2.
Ad es. per analizzare 100.000.001 mi fermerei a 10.000, o meglio a 10001, senza continuare fino a 50.000.000.
Ciao a tutti.
Tony

[Giovanni]

Ciao a tutti
I numeri primi nella forma 2^n-1 con n=numero primo sono i numeri di Mersenne ed esiste un progetto, il progetto G.I.M.P.S., che lavora a questa ricerca.
Il programma esiste già, lo puoi trovare all'indirizzo www.gimps.it
Registrandoti puoi partecipare anche tu alla ricerca.

Giovanni.

[tony]

Rettifico il mio msg di poco fa.
Mi è scappato un errore: la cifra 10001 va letta 10007.

Cioé: per trovare con forza bruta i primi fino a 100 milioni
basta ] generare i primi 2, 3, 5, ..., 10007 (che è il primo primo maggiore di sqrt(10^8) )

tony