Algoritmo per trovare numeri primi:
Inviato: 20/06/2017, 16:54
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.
la parte un po' più grottesca dell'algoritmo è quel
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!
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)));
Codice: Seleziona tutto
sqrt(t)/logn(11,t)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!