Algoritmo per trovare numeri primi:

Algoritmi, discussioni sulle possibili implementazioni, matematica, fisica e tutti gli argomenti correlati alla programmazione
Rispondi
Avatar utente
boxbuilder
Membro
Messaggi: 158
Iscritto il: 25/06/2015, 10:37
Specialità: programmatore
Uso: GM:Studio 1.4 HTML5
Contatta:

Algoritmo per trovare numeri primi:

Messaggio da boxbuilder »

ciao vi allego un banale script per il calcolo dei numeri primi, che vanno da 0 a 100000 (9592)
Ho usato il crivello di Eratostene, ma so che ci sono altri metodi molto più performanti.
Se volete contribuire mi piacerebbe vedere qualche algoritmo più intelligente.

Codice: Seleziona tutto

//trova i numeri primi da 0 a max_value:
var max_value = 100000;

//crivello di Eratostene:
primi = ds_list_create();

for(var i = 2 ; i < max_value ; i++) {
   ds_list_add(primi, i);
}

var t = ds_list_size(primi);
var c = 0;

for(var j = sqrt(t)/logn(11,t); j > 0; j--){
    for(var i = 0; i < t; i++){
        if((primi[| i] != primi[| c])&&(primi[| i] % primi[| c] == 0)){
            ds_list_delete(primi, i);
            t--;
        }
    }
    c++;
}

show_debug_message("N primi trovati: "+ string(ds_list_size(primi)));
la parte un po' più grottesca dell'algoritmo è quel

Codice: Seleziona tutto

sqrt(t)/logn(11,t)
dato che π(x) = Li(x) + O(sqrt(c)ln(x))
ho approssimato usando il logaritmo su base 11 di x , vi sembrerà incredibile, ma funziona benissimo come sostituto di Li(x) magari facendo cose a casaccio, senza volerlo ho scoperto una nuova proprietà dei numeri primi che mi farà diventare ricco e famoso.

ciao e a presto!

Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Algoritmo per trovare numeri primi:

Messaggio da Barnack »

wait che intendi con "da 0 a 100'000 (9592)"? 9592 è primo? XD

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Avatar utente
ball-man_3000
Moderatore
Messaggi: 1263
Iscritto il: 26/08/2009, 13:42
Specialità: Contare con le dita
Uso: GM:Studio 2
Località: Bologna
Contatta:

Re: Algoritmo per trovare numeri primi:

Messaggio da ball-man_3000 »

molto carino. Devo dire che ci ho messo un attimo a decifrarlo in quanto ci sono una serie di cicli non troppo intuitivi. La tua approssimazione da quanto sembra diminuisce leggermente il numero di cicli di "pulizia" cui la lista è sottoposta, ovvero diminuisce il numero di numeri primi che assumi ci siano nel range preso. Questo mi fa presupporre che in realtà l'approssimazione derivi dal range preso. Se invece di 100'000 prendessi 100'000'000 ad esempio, pensi che potrebbe ancora funzionare? Non sono stato a fare test ma forse avrebbe bisogno di un'aggiustatina, o forse questo bisogno comincia a sentirsi solo proseguendo verso range molto maggiori(vista la natura irregolare ma sempre più sporadica della distribuzione di questi numeri).
Simpatico l'exploit/spiegazione con il logaritmo integrale.
Per quanto riguarda altri algoritmi, io mi ero intrippato qui:
https://en.wikipedia.org/wiki/Sieve_of_Atkin
Quattro corde sono meglio

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti