Mostra i numeri primi
Un valore intero maggiore di 1 si definisce primo se non può essere diviso, senza resto, da nessun numero ad eccezione di 1 e se stesso.
In altre parole, n > 1 è primo se non può essere diviso da nessun altro numero ad eccezione di 1 e n.
Ad esempio, 5 è primo perchè non può essere diviso senza resto da 2, 3 o 4.
scrivi un codice che mostri i numeri primi nell’intervallo da 2 a n.
Per n = 10 il risultato sarà 2,3,5,7.
P.S. Il codice dovrebbe funzionare per qualsiasi numero n, non solo per un valore numerico prefissato.
Ci sono diversi possibili algoritmi per il nostro scopo.
Usiamo un ciclo annidato:
For each i in the interval {
check if i has a divisor from 1..i
if yes => the value is not a prime
if no => the value is a prime, show it
}Il codice usa un’etichetta:
let n = 10;
nextPrime:
for (let i = 2; i <= n; i++) { // per ogni i...
for (let j = 2; j < i; j++) { // controlla i suoi divisori..
if (i % j == 0) continue nextPrime; // se è divisibile per uno di essi, non è un numero primo; passa a prossima iterazione
}
alert( i ); // un numero primo
}Ci sono molti modi per ottimizzare questo algoritmo. Ad esempio, potremmo controllare i divisori di 2 fino alla radice di i. In ogni caso, se vogliamo essere veramete efficenti su grandi intervalli, abbiamo bisogno di cambiare approcio ed affidarci ad algoritmi matematici più avanzati e complessi, come Quadratic sieve, General number field sieve etc.