Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Un test di primalità serve a definire se un numero diverso da uno è primo cioè divisibile solo per se stesso e per uno. Un primitivo codice potrebbe essere :
Codice sorgente - presumibilmente Algoritmi
primo(n)
m=1,div=0;
while(m<=n)
{
if(n%m==0)div++;
m++;
}
if(div==2)return true;
else return false;
end primo
Una semplice ottimizzazione verrebbe in mente a chiunque, cioè che nessun numero puo essere divisibile per un numero maggiore della sua metà per cui
Codice sorgente - presumibilmente Algoritmi
m=1,div=0;
while(m<=n/2)
{
if(n%m==0)div++;
m++;
}
if(div==1)return true;
else return false;
end primo
Ma siccome io l'altro ieri non avevo niente di meglio da fare io scritto questo
Codice sorgente - presumibilmente Algoritmi
primo(n)
if(n<=3)return true;
m=2;
while(m<=(n\m))
{
if(n%m==0)return false;
m++;
}
return true
Che non solo si ferma se trova un numero per cui n è divisibile, ma via via restringe la quantità di numeri controllati diminuendo le iterazioni, perchè se n non è disibile per 2 non sarà divisibile neanche per la sua metà e così per tutti gli altri numeri e questo rende molto più veloce l'algoritmo. Inoltre con una piccola modifica si può rendere il procedimento utile per la fattorizzazione semplicemente ritornando n se il numero è primo o m se n è divisibile per m.
Apparte il fatto che l'ultimo algoritmo interrompe eccome il ciclo, viavia restringe il tutto per cui anche se non è divisibile per 3i numeri possibili diventeranno un 1/3 del numero originale se non è divisibile per 5 allora saranno 1/5 e la radice quadrata sarebbe la migliore se il calcolo fosse più veloce e la divisione già di per sé è lenta per cui . . .
ps: la radice quadrata o la radice cubica o la radice n sarebbero tutte possibili perchè se non è divisibile per due non lo è neanche per 4 8 16 32 e tutti multipli di 2 e allora si torna al crivello di Eratostene, cioè per sapere + velocemente se un numero è primo dovresti saperlo anche di tutti i numeri minori di lui !!!
Ultima modifica effettuata da lorelapo il 19/05/2007 alle 17:47
sul ciclo scusa avevo visto dopo ho appunto editato.
con la radice intendevo che la condizione che un numero non sia primo necessita di almeno due numeri che lo dividono uno oltre e uno prima ( o coincidenti ) della sua radice quadrata. se non ne hai trovato uno prima della sua radice quadrata non è possibile che ne sia uno dopo perchè non potrebbe più avere la corrispondenza prima.
era un modo x eliminare casi superflui.
È ovvio che non ci volesse tanto a semplificare il codice, il potenziamento è però la cosa più importante dell'algoritmo sopra, Black Shadow la tua versione più sintetica ed ugualmente veloce (come l'ho scritta io in C) ma qui cercavo solo di rendere più comprensibile il codice, cmq grazie per aver postato.
| 
e la divisione già di per sé è lenta per cui . . .
