Ricerca numeri primi
Ricerca numeri primi
Mi viene richiesto, dato un numero, di trovare tutti i numeri primi che lo precedono...
E' una cosa fattibile?
Io sapevo (forse erroneamente) che i numeri primi non seguono una precisa legge matematica... quindi ocme potrei trovarli?
Grazie
E' una cosa fattibile?
Io sapevo (forse erroneamente) che i numeri primi non seguono una precisa legge matematica... quindi ocme potrei trovarli?
Grazie
- Decan
- Messaggi: 48
- Iscritto il: 01 gen 1970, 01:00
- Località: San Martino Valle Caudina (AV)
- Contatta:
Se si tratta di scrivere un programma per trovarli (credo sia questo che vuoi fare, se hai postato in questa sezione!), è facile...
1) Crea una matrice unidimensionale abbastanza grande per contenere tutti i numeri primi fino al tuo numero massimo, n (non ricordo a quale limite tende il rapporto (numero dei primi minori di n)/n ). Poni il primo numero della matrice uguale a 2. Gli altrinumeri primi li troverai in seguito.
2) Per ogni numero x<=n, controlla la divisibilità di x per i numeri primi nella matrice (se vuoi provare a velocizzare la cosa, controlla la divisibilità solo per i numeri primi che non superino sqrt(x): nella matrice ci sono tutti, qualunque sia x, e ora ti dico perché); non appena x risulta divisibile per uno di questi primi, passa a x+1. Se nessuno di questi numeri divide x, vuol dire che x è primo: inseriscilo nella matrice, alla prima posizione libera.
3)alla fine dell'analisi, avrai tutti i numeri primi <=n.
Probabilmente ho fatto la scoperta dell'acqua calda e tu ti aspettavi qualcosa di più veloce, ma in questo caso non so che risponderti (anzi, sono d'accordo con te). Comunque io un programma per trovare i numeri primi l'ho fatto esattamente così.
1) Crea una matrice unidimensionale abbastanza grande per contenere tutti i numeri primi fino al tuo numero massimo, n (non ricordo a quale limite tende il rapporto (numero dei primi minori di n)/n ). Poni il primo numero della matrice uguale a 2. Gli altrinumeri primi li troverai in seguito.
2) Per ogni numero x<=n, controlla la divisibilità di x per i numeri primi nella matrice (se vuoi provare a velocizzare la cosa, controlla la divisibilità solo per i numeri primi che non superino sqrt(x): nella matrice ci sono tutti, qualunque sia x, e ora ti dico perché); non appena x risulta divisibile per uno di questi primi, passa a x+1. Se nessuno di questi numeri divide x, vuol dire che x è primo: inseriscilo nella matrice, alla prima posizione libera.
3)alla fine dell'analisi, avrai tutti i numeri primi <=n.
Probabilmente ho fatto la scoperta dell'acqua calda e tu ti aspettavi qualcosa di più veloce, ma in questo caso non so che risponderti (anzi, sono d'accordo con te). Comunque io un programma per trovare i numeri primi l'ho fatto esattamente così.
"I' vo gridando: pace, pace, pace!" (F. Petrarca)
Presidente dell'EATO
Membro della Lega anti-Mickey Mouse 2
Presidente dell'EATO
Membro della Lega anti-Mickey Mouse 2
$ ~\pi(x) $ la funzione che ti da' il numero di numeri primi minori di $ ~x $ e' asintotica a $ ~\frac{x}{\ln{x}} $
Giocherellando coi fit ho trovato
$ \displaystyle \approx \frac{1.057x}{\ln{.54x}} $
$ \qquad\displaystyle \approx \frac{(1-a)x}{\log{ax}} $ con $ ~a\approx .541378 $
il metodo suggerito da Decan penso sia il migliore o uno dei migliori per x non troppo grande
per qualcosa di piu' guarda anche qui, che ci sono vari link a varie risorse
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=6655
Giocherellando coi fit ho trovato
$ \displaystyle \approx \frac{1.057x}{\ln{.54x}} $
$ \qquad\displaystyle \approx \frac{(1-a)x}{\log{ax}} $ con $ ~a\approx .541378 $
il metodo suggerito da Decan penso sia il migliore o uno dei migliori per x non troppo grande
per qualcosa di piu' guarda anche qui, che ci sono vari link a varie risorse
http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=6655
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
puoi decidere se:
a) trovato un numero primo metterlo nella matrice e alla fine stampare tutti i numeri della matrice
b) trovato un numero primo metterlo nella matrice e stamparlo
il secondo metodo e' piu' efficiente perche' necessita di un solo ciclo.
a) trovato un numero primo metterlo nella matrice e alla fine stampare tutti i numeri della matrice
b) trovato un numero primo metterlo nella matrice e stamparlo
il secondo metodo e' piu' efficiente perche' necessita di un solo ciclo.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Re: Ricerca numeri primi
Infatti tutti sanno che i numeri primi sono completamente casuali.Sosuke ha scritto:Io sapevo (forse erroneamente) che i numeri primi non seguono una precisa legge matematica...
Del resto, lo dice anche Umberto Eco: http://linuz.sns.it/~vigliett/UmbertoEco.jpg.
http://it.wikipedia.org/wiki/Ironia11:11 ha scritto:Non direi proprio che i numeri primi siano "completamente casuali"
piu' che altro cio' vuol dire che per $ ~p>3 $ non sono multipli di 2 e di 3 (ovviamente)11:11 ha scritto:per ogni numero primo p>3 si ha:
$ p \equiv 1 \mod 6 $
oppure
$ p \equiv -1 \mod 6 $
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
uhm forse no... però ci provo... forse è una sequenza che no segue una legge matematica... nel caso dei numeri primi è una sequenza in cui non si può trovare il successore, il precedente o l'n-simo numero successivo a quello dato tramite una formula...edriv ha scritto:Faresti prima a cercare di capire la tua frase... ciòè, voglio dire che tu non sai cosa intendi dicendo "casuale".
Sapresti dire matematicamente (o comunque senza giri di parole) cos'è, secondo te, una sequenza casuale?
non saprei onestamente...