Ricerca numeri primi

Programmazione, algoritmica, teoria dell'informazione, ...
Sosuke
Messaggi: 256
Iscritto il: 05 ago 2006, 20:10

Ricerca numeri primi

Messaggio da Sosuke » 19 nov 2006, 10:27

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

Avatar utente
Decan
Messaggi: 48
Iscritto il: 01 gen 1970, 01:00
Località: San Martino Valle Caudina (AV)
Contatta:

Messaggio da Decan » 19 nov 2006, 11:53

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 :oops:). 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

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 19 nov 2006, 19:43

$ ~\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
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

Sosuke
Messaggi: 256
Iscritto il: 05 ago 2006, 20:10

Messaggio da Sosuke » 19 nov 2006, 23:48

ma non capisco una cosa... visto che la matrice uni dimensionale la devo riempire comunque io, a quel punto non mi converrebbe scansionare e stampare tutti i numeri della matrice finchè v[x]<n (con v[x] il numero primo della matrice unidimensionale e n il mio numero) ??

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 20 nov 2006, 00:02

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.
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

Sosuke
Messaggi: 256
Iscritto il: 05 ago 2006, 20:10

Messaggio da Sosuke » 20 nov 2006, 00:08

Ahhh ho capito... per non dover inizializzare la matrice in fase di progettazione... comunque interessante questo metodo per trovare i numeri primi..

MindFlyer

Re: Ricerca numeri primi

Messaggio da MindFlyer » 20 nov 2006, 19:57

Sosuke ha scritto:Io sapevo (forse erroneamente) che i numeri primi non seguono una precisa legge matematica...
Infatti tutti sanno che i numeri primi sono completamente casuali. :?
Del resto, lo dice anche Umberto Eco: http://linuz.sns.it/~vigliett/UmbertoEco.jpg.

11:11
Messaggi: 2
Iscritto il: 29 nov 2006, 08:08
Località: Milano

Messaggio da 11:11 » 29 nov 2006, 12:00

Non direi proprio che i numeri primi siano "completamente casuali", basta pensare alla densità asintotica $ ~\pi(x)\approx\ x/lnx $
o al semplice fatto che per ogni numero primo p>3 si ha:
$ p \equiv 1 \mod 6 $
oppure
$ p \equiv -1 \mod 6 $

Saluti
[tex]1^3+5^3+3^3=153[/tex]

MindFlyer

Messaggio da MindFlyer » 29 nov 2006, 18:38

11:11 ha scritto:Non direi proprio che i numeri primi siano "completamente casuali"
http://it.wikipedia.org/wiki/Ironia

11:11
Messaggi: 2
Iscritto il: 29 nov 2006, 08:08
Località: Milano

Oops...

Messaggio da 11:11 » 29 nov 2006, 19:52

ha ha, buona questa, non avevo colto... certo il riferimento ad Umberto Eco avrebbe dovuto mettermi sulla buona strada.
Grazie comunque, non è mai troppo tardi!
[tex]1^3+5^3+3^3=153[/tex]

Sosuke
Messaggi: 256
Iscritto il: 05 ago 2006, 20:10

Messaggio da Sosuke » 29 nov 2006, 19:59

non ho più capito io invece... sono o no casuali sti cosi???

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 29 nov 2006, 20:25

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?

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 29 nov 2006, 21:56

11:11 ha scritto:per ogni numero primo p>3 si ha:
$ p \equiv 1 \mod 6 $
oppure
$ p \equiv -1 \mod 6 $
piu' che altro cio' vuol dire che per $ ~p>3 $ non sono multipli di 2 e di 3 (ovviamente)
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

Sosuke
Messaggi: 256
Iscritto il: 05 ago 2006, 20:10

Messaggio da Sosuke » 30 nov 2006, 14:32

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?
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...

non saprei onestamente...

Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo » 30 nov 2006, 22:56

Per la gioia di Mind consiglio un attento studio del teorema di Van der Waerden per vedere che anche se una sequenza è casuale segue comunque regolarità :D
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph

Rispondi