[*]: Algoritmo per determinare se un numero è primo

[ascatem2]

Mi interesserebbe sapere qual'è l'algoritmo migliore che, dato un numero intero, mi dice se è primo.

grazie.

[devil89]

In che linguaggio?

[alka]

Originariamente inviato da devil89
In che linguaggio?

Suppongo sia indifferente, visto che non è stato indicato.

[ascatem2]

Originariamente inviato da devil89
In che linguaggio?

un'algoritmo è un algoritmo.... me lo puoi fare anche in italiano, se è buono poi lo codifichi come vuoi.

Ovvio che non voglio il tipico dato il nuemro n, provo a dividerlo per tutti i suoi predecessori.

thanks

[devil89]

Hai ragione alka. Non me ne ero accorto.

ascatem2<<<
Potresti far un controllo del tipo:

if(num!=2 && num!=3) {
           if(num%2==0 || num%3==0)
                   il numero non è primo 
            else E' primo.
} else
           E' primo

[ascatem2]

Originariamente inviato da devil89
Hai ragione alka. Non me ne ero accorto.

ascatem2<<<
Potresti far un controllo del tipo:

if(num!=2 && num!=3) {
           if(num%2==0 || num%3==0)
                   il numero non è primo 
            else E' primo.
} else
           E' primo

mmm non ha molto senso, se è 35??(7*5) il tuo alg direbbe che è primo...

[ascatem2]

il primo algoritmo, quello + banale è questo:

da indice=2 a difetto(num/2)
se (num MOD indice) =0
non primo; interrompi programma

numero primo, restituisci primo

un secondo algoritmo che non so se sia prettamente corretto è:

da indice=2 a radiceQuadrata(num)
se (num MOD indice) =0
non primo; interrompi programma

numero primo, restituisci primo



non sono sicuro che sia corretto.

[ascatem2]

Originariamente inviato da ascatem2
il primo algoritmo, quello + banale è questo:

da indice=2 a difetto(num/2)
se (num MOD indice) =0
non primo; interrompi programma

numero primo, restituisci primo

un secondo algoritmo che non so se sia prettamente corretto è:

da indice=2 a radiceQuadrata(num)
se (num MOD indice) =0
non primo; interrompi programma

numero primo, restituisci primo



non sono sicuro che sia corretto.

da 1 a 500000 funziona, ora provo finoa 2.000.000, comunque penso che la dimostrazione ddel secondo sia semplice, la sto appurando or ora

in ogni caso, non esiste di meglio?

[devil89]

Potresti usare un algoritmo che consente di individuare tutti i numeri primi minori di un certo numero dato che stabilisce come limite del tuo programma.

Potresti per esempio memorizzare in un array tutti i numeri fino al limite che stabilisci.

1. Si prende il numero più piccolo nella lista. Questo è un numero primo (all'inizio è 2, ed è ovvio che sia primo) e fa parte della soluzione.

2. Si cancella il numero primo trovato e tutti i suoi multipli.
Se il numero trovato è minore della radice quadrata di N, ripeti il punto 1
altrimenti
L'algoritmo è terminato. I numeri primi sono tutti quelli trovati, più quelli che rimangono non cancellati nella lista.

A questo punto gli fai un controllo all'interno della lista se è presente il numero inserito.

[ascatem2]

Originariamente inviato da devil89
Potresti usare un algoritmo che consente di individuare tutti i numeri primi minori di un certo numero dato che stabilisce come limite del tuo programma.

Potresti per esempio memorizzare in un array tutti i numeri fino al limite che stabilisci.

1. Si prende il numero più piccolo nella lista. Questo è un numero primo (all'inizio è 2, ed è ovvio che sia primo) e fa parte della soluzione.

2. Si cancella il numero primo trovato e tutti i suoi multipli.
Se il numero trovato è minore della radice quadrata di N, ripeti il punto 1
altrimenti
L'algoritmo è terminato. I numeri primi sono tutti quelli trovati, più quelli che rimangono non cancellati nella lista.

A questo punto gli fai un controllo all'interno della lista se è presente il numero inserito.

una sèpece di crivello di erastostene, troppo laborioso... cercavo qualcosa con complessità inferiore a O(radq(n)) qualcosa tipo O(log(n)), ammesso che esista.