numeri primi al computer...

[germania2002]

premetto che è un problema sicuramente scemo e la soluzione non l\'ho ancora calcolata.
<BR>
<BR>Un programmatore scemo (che sarei io) vuole scrivere (in Pascal) un programma per la ricerca di numeri primi.
<BR>Poichè è ancora molto inesperto e non sa molte nozioni sull\'informatica, non usa alcuna funzione che faccia memorizzare al pc i numeri primi trovati (per usarli nella ricerca del n. primo successivo), quindi il pc ogni volta dovrà dividere un numero dato \"q\" per tutti i numeri tali che: 1< n < q
<BR>
<BR>Il programmatore, però, scemo scemo non è fa alcune modifiche all\'algoritmo:
<BR>-Dividerà il numero q per tutti i numeri tali che 1<(2k+1)<(q/2 +1)
<BR>-Ogni numero esaminato sarà prodotto dall\'equazione: q=2n+1 (con n via via crescente ovviamente), quindi q sarà sempre dispari
<BR>-I numeri pari vengono saltati
<BR>-Si iniziano ad esaminare i numeri da 3.
<BR>-Il ciclo della divisione inizia con due(*1) come eccezione e poi prosegue con 2n+1 con n₀= 1
<BR>
<BR>Alla fine, il programma funziona, e per prova il programmatore lo fa arrivare fino ad un numero qmax=10.000.
<BR>Qunate divisioni avrà fatto il computer per trovare tutti i numeri primi compresi tra 2 e 10.000??
<BR>
<BR>*1: Non serve ad una cippa iniziare con due per tutti i numeri, poichè si procede con numeri dispari....errore mio (si dice:\"sbagliando s\'impara\", credo che per me non valga). Servirebbe solo per verificare che 3 è primo (visto che uno non si esamina).
<BR>
<BR>PS: ma vedi un pò che caspita di problemi contorti che mi escono, nemmeno alle elementari fanno ste cose......
<BR>PPS: se qualche anima pia non si rovescia vedendo stò problema (uno dei pochi che mi escono dalla testa), può tentare una generalizzazione del problema???
<BR>PPPS: non uccidetemi <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>\"un uomo deve migliorare di qualcosa il mondo, se si vuole sentire realizzato...\"
<BR>\"Deutschland der beste Staat!\"
<BR><!-- BBCode Start --><A HREF="http://www.grid.org" TARGET="_blank">www.grid.org</A><!-- BBCode End --> (pc vs cancro,sars,peste)<BR><BR>[ Questo Messaggio è stato Modificato da: germania2002 il 26-02-2004 11:02 ]

[bh3u4m]

Non è necessario dividerlo per tutti i numeri e verificare che il resto sia diverso da zero per verificare che sia primo.
<BR>Supponiamo che MAX sia il valore massimo della tua ricerca.
<BR>Basta creare un vettore che contiene i numeri primi in successione da 2 a n (n tale che n² >= MAX), il che abbrevia molto la ricerca, e provare a dividere per tutti gli elementi di questo vettore.
<BR>
<BR>
<BR>

[bh3u4m]

Comunque il numero di divisioni del tuo programma sarà:
<BR>
<BR>((Somma totale numeri primi da 2 a 10000) + (Numero di numeri primi))/2
<BR>
<BR>Credo che non esista un metodo per determinate la somma di tutti i numeri primi in un certo intervallo, né il loro numero.
<BR>Forse Gauss aveva trovato un metodo, ma era approssimativo.
<BR>
<BR>PS: Qualcuno conosce questo metodo?

[euler_25]

Difatti non esiste, hai detto bene! Sì come non esiste una formula <!-- BBCode Start --><I>easy to use</I><!-- BBCode End --> per generare numeri primi... se si esclude chiaramente la celeberrima <!-- BBCode Start --><B>formula di Gandhi</B><!-- BBCode End -->, di per sè interessante ma praticamente inutile, che consente (in teoria) di ottenere il termine di posto (n+1)-esimo nella successione {p_n} dei numeri primi (n intero > 0), noti che siano p₁, p₂, ..., p_n, con p₁ := 2.
<BR>
<BR>In quanto al numero di primi contenuti entro un certo intervallo... una formula <!-- BBCode Start --><I>esatta</I><!-- BBCode End --> effettivamente non esiste, ma è possibile fornirne una stima asintotica basata sul cosiddetto teorema dei numeri primi, secondo il quale la cardinalità dell\'insieme dei primi minori o uguali di un certo x reale > 0, per x --> +inf, è ben approssimata dalla funzione π(-): R⁺ --> R: x --> x/ln(x), ove ln(-) denota il logaritmo neperiano. Questo teorema, enunciato primieramente dal solito Gauss, venne dimostrato solo più tardi, e indipendentemente, da Hadamard e De La Vallèe Poussin, come peraltro già detto nel 3d \"Il teorema più bello\", che invito tutti pertanto a riguardare giusto per risparmiarmi dal copia-incollare qui informazioni già fornite altrove!
<BR>
<BR>EDIT: per chi si volesse veramente sbizzarrire, aggiungo che esiste almeno un\'altra formula in grado di generare, almeno in teoria, una successione {q_n}, non definitivamente costante, di soli numeri primi, il cui termine generale è definito direttamente in funzione della variabile n attraverso tutta una serie di operazioni razionali e di arrotondamento applicate sulla <!-- BBCode Start --><B>costante di Brun</B><!-- BBCode End -->.<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 26-02-2004 01:55 ]

[germania2002]

Tò, un problema che avevo pensato fosse una cazzata in realtà è irrisolvibile???
<BR>No mi pare strano!!!
<BR>Cacchio dò un inizio ed una fine della ricerca. Insomma parto da 3 e voglio arrivare fino a q=100.
<BR>il computer dovrà esaminare tutti i numeri naturali dispari compresi tra 3 (incluso) e 100(incluso) --> [3;100], e dividerli per tutti i numeri numeri dispari tali che: (2n+1)<=(q/2+1)...
<BR>Voi dite, c\'è questa formula qui, ma se questa formula si basa sulla quantità (non calcolabile) dei numeri primi trovati!!! Non esiste una che si basa sui numeri dati (cioè i numeri naturali dispari dell\'intervallo [3;n])???[addsig]

[bh3u4m]

La soluzione migliore è modificare il programma affinché conti il numero di divisioni.

[germania2002]

um si, però io volevo far fare l\'esercizio qui (dato che è una cazzata), non al pc!!![addsig]