Numeri primi
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
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
Risposte
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
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
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
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
Io tifo x te!!! così mi dai una %... 
Mi unisco al 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
hehehe grazie
cmq quando ho finito il programmino lo linko su un post cosi' chi vuole puo' tenerlo un po' acceso quando vuole
cmq quando ho finito il programmino lo linko su un post cosi' chi vuole puo' tenerlo un po' acceso quando vuole
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
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
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.
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.
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
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
Thx giovanni....
Come si dimostra che se un divisore nn lo trovi prima di sqrt(n) nn lo trovi piu'?
forza goblin sbizzarrisciti
Come si dimostra che se un divisore nn lo trovi prima di sqrt(n) nn lo trovi piu'?
forza goblin sbizzarrisciti
I numeri primi proprio non sono il mio forte... lascio il campo agli esperti e imparo...
Ciao.
Lunaxv chiede
"Come si dimostra che se un divisore nn lo trovi prima di sqrt(n) nn lo trovi piu'?"
Direi che, se a=p*q e q>sqrt(a) allora p
In poche parole, se cerchi di scomporre 97, non arrivi a provare a dividere per 11.
Tony
Lunaxv chiede
"Come si dimostra che se un divisore nn lo trovi prima di sqrt(n) nn lo trovi piu'?"
Direi che, se a=p*q e q>sqrt(a) allora p
In poche parole, se cerchi di scomporre 97, non arrivi a provare a dividere per 11.
Tony
citazione:
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
Ciao!
Se ti interessa e' partito da poco il Project Billion Digits, sponsorizzato dal GIMPS Italia! Stiamo fattorizzando numeri di Mersenne da almeno un miliardo di cifre, eliminando tuttiquelli che hanno almeno un fattore noto. Il progetto distribuito ha utenti da diverse parti del mondo, ed il programma su cui poggia e' italiano (lo ho scritto io...). Un pizzico di sano orgoglio nazionale nel campodella ricerca matematica!
Il link e' il seguente: http://www.gimps.it/billion/billion.htm
Se vi interessa e volete saperne di piu' c'e' il mio email sulla pagina.
Luigi Morelli
ehi luna, perchè non provi a dimostrare la congettura di goldbach? così te ne danno 2 milioni di dollari!
a proposito di numeri primi, non avevano scoperto un polinomio, in 26 variabili, che genera solo numeri primi? potrebbero usare quello per trovarne di altri..
A proposito di numeri perfetti,ovvero di
numeri che sono uguali alla somma di tutti loro
divisori [incluso l'1 ed escluso ,ovviamente, il numero
medesimo ],propongo questo problema(forse
gia' noto):
Dimostrare che se per qualche intero m il numero
2^(m+1)-1 e' primo, allora il numero
2^m*(2^(m+1)-1) e' un numero perfetto.
La dimostrazione non richiede alcuna nozione di
Teoria dei Numeri,
Complimenti a Lunaxv che ha cosi' in "non cale"
il " vil denaro":io non ci riesco!
karl.
numeri che sono uguali alla somma di tutti loro
divisori [incluso l'1 ed escluso ,ovviamente, il numero
medesimo ],propongo questo problema(forse
gia' noto):
Dimostrare che se per qualche intero m il numero
2^(m+1)-1 e' primo, allora il numero
2^m*(2^(m+1)-1) e' un numero perfetto.
La dimostrazione non richiede alcuna nozione di
Teoria dei Numeri,
Complimenti a Lunaxv che ha cosi' in "non cale"
il " vil denaro":io non ci riesco!
karl.
citazione:
a proposito di numeri primi, non avevano scoperto un polinomio, in 26 variabili, che genera solo numeri primi? potrebbero usare quello per trovarne di altri..
La formula e' stata discussa su Hans Riesel, "Prime Numbers and Computer Methods for Factorization", pag. 39 e 40 della seconda edizione, ed il volume di "CRC Standard Mathematical Tables and Formulae", 30ma editione, pagina 94.
Riesel parla di polinomi "produttori di primi": uno dei primi fu defi nito (manco a dirlo) da Eulero, x^2-x+41, che produce primi per x=0,1,2...40. Ovviamente per x=41 la parte "-x+41" si annulla, lasciando un quadrato perfetto.
Esiste un teorema provato secondo il quale, a prescindere dalle variabili, nessun polinomio puo' produrre SOLO numeri primi: ovvio che quando si ha a che fare con numeri di 10 milioni di cifre dei quali non si conosce la primalita', un tale polinomio risulta inutile. Ma ne esiste un altro secondo il quale esistono formule (non polinomiali) che in effetti producono solo primi. Mills, nel 1947, ha mostrato che esiste un numero reale theta in (1,2) tale che per ogni intero positivo n, il numero floor(theta^3^n) e' primo (Crandall-Pomerance, "Prime numbers: a computational perspective").
Ad ogni mod, nessuna delle formule note di questo tipo risulta pratica per "trovare" primi, ed in particolare primi di grandezza record.
Per curiosita', la formula a 26 variabili risulta essere la seguente:
(k+2){1-[wz+h+j-q]²-[(gk+2g+k+1)(h+j)+h-z]²-[2n+p+q+z-e]²
-[16(k+1)³(k+2)(n+1)²+1-f²]²-[e³(e+2)(a+1)²+1-o²]²-[(a²-1)y²+1-x²]²
-[16r²y^4(a²-1)+1-u²]²-[((a+u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²]²
-[n+l+v-y]²-[(a²-1)l²+1-m²]²-[ai+k+1-l-i]²-[p+l(a-n-1)+b(2an+2a-n²-2n-2)-m]²
-[q+y(a-p-1)+s(2ap+2a-p²-2p-2)-x]²-[z+pl(a-p)+t(2ap-p²-1)-pm]²}
Luigi Morelli
per Karl: sono quasi certo che il risultato cui accenni sia stato dimostrato da Eulero.
ciao, ubermensch
ciao, ubermensch
Per Cygni_61.
Dopo aver visto la formula,mi sto ancora chiedendo
se c'e' un confine per la mente.
Per Uber.
Sicuramente il grande Eulero ci avra' lavorato sopra e chissa'
che ne avra' tirato fuori.Tuttavia nel nostro caso
ho una soluzione assai elementare:se nessuno si scomoda,
magari la posto.
Saluti ad entrambi.
karl.
Dopo aver visto la formula,mi sto ancora chiedendo
se c'e' un confine per la mente.
Per Uber.
Sicuramente il grande Eulero ci avra' lavorato sopra e chissa'
che ne avra' tirato fuori.Tuttavia nel nostro caso
ho una soluzione assai elementare:se nessuno si scomoda,
magari la posto.
Saluti ad entrambi.
karl.
La dimostrazione del problema posto da Karl:
Si esegue una scomposizione in fattori primi per trovare appunto i divisori dei numeri 2^m e 2^(m+1)-1, che sono:
1, 2^1, 2^2, 2^3, ..., 2^m;
2^(m+1)-1, 2^1 (2^(m+1)-1), 2^2 (2^(m+1)-1), ..., 2^m (2^(m+1)-1)
La somma di questi numeri (escluso l'ultimo), è pertanto:
S(m) + S(m-1)(2^(m+1)-1)
Dove S(m) è una progressione geometrica di ragione 2 fino a 2^m. Poiché S(m) = 2^(m+1)-1, la somma diventa:
2^(m+1) - 1 + (2^m - 1)(2^(m+1) - 1) =
= (1 + 2^m - 1)(2^(m+1) - 1) =
= 2^m (2^(m+1) - 1)
Che è proprio il nostro numero, che risulta pertanto essere un numero perfetto.
Si esegue una scomposizione in fattori primi per trovare appunto i divisori dei numeri 2^m e 2^(m+1)-1, che sono:
1, 2^1, 2^2, 2^3, ..., 2^m;
2^(m+1)-1, 2^1 (2^(m+1)-1), 2^2 (2^(m+1)-1), ..., 2^m (2^(m+1)-1)
La somma di questi numeri (escluso l'ultimo), è pertanto:
S(m) + S(m-1)(2^(m+1)-1)
Dove S(m) è una progressione geometrica di ragione 2 fino a 2^m. Poiché S(m) = 2^(m+1)-1, la somma diventa:
2^(m+1) - 1 + (2^m - 1)(2^(m+1) - 1) =
= (1 + 2^m - 1)(2^(m+1) - 1) =
= 2^m (2^(m+1) - 1)
Che è proprio il nostro numero, che risulta pertanto essere un numero perfetto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo