Ricerca numeri primi

[Sosuke]

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

[Decan]

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

[SkZ]

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

[Sosuke]

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

[SkZ]

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.

[Sosuke]

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

[MindFlyer]

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]

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

[MindFlyer]

Non direi proprio che i numeri primi siano "completamente casuali"

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

[11:11]

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!

[Sosuke]

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

[edriv]

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?

[SkZ]

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)

[Sosuke]

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

[Sisifo]

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à