Un algoritmo in un giorno : Come verificare se un numero primo in JavaScript

Marina Shemesh
Marina Shemesh

Seguire

28 Maggio 2020 · 7 min a leggere

e ‘ quasi garantito che almeno una volta nella codifica istruzione vi verrà chiesto di scrivere qualche tipo di funzione che coinvolge numeri primi. Si tratta di un esercizio popolare in codifica boot camp e talvolta anche pop-up in colloqui di lavoro.

Cosa sono i numeri primi?

Un numero primo è un numero naturale maggiore di 1 i cui unici fattori sono 1 e il numero stesso. Cioè, può essere diviso in parti uguali solo per 1 e se stesso.

I numeri naturali sono numeri interi positivi come 1, 5, 201, 229999 ecc. Il numero 0, frazioni, decimali e numeri negativi non sono numeri naturali.

Il numero 5 è un numero primo perché i suoi UNICI fattori sono 1 e 5. Non c’è altro modo per ‘creare’ il numero 5.

Il numero 4 non è un numero primo perché 2 x 2 ci dà anche 4.

Il numero 20 non è un numero primo perché 5 x 4 ci dà anche 20, così come 2 x 10.

I numeri primi non sono mai pari (tranne che per 2)

Uno dei modi più rapidi per verificare se un numero è un numero primo o meno è quello di verificare se è un numero pari. Se un numero può essere diviso per 2 senza lasciare un resto non soddisfa più la definizione per un numero primo — un numero che può essere diviso in parti uguali solo per 1 e se stesso.

In JavaScript possiamo controllare i numeri pari usando l’operatore modulo (%).

L’operatore modulo restituisce il resto dopo che un intero è stato diviso per un altro.
Ad esempio 12% 5 restituisce 2.
E 59% 5 restituisce 4.

Se dividi un numero intero per 2 e il resto è 0, sappiamo che il numero intero è un numero pari.

Ad esempio 10% 2 = 0
E 2200 % 2 = 0

in JavaScript sarà simile a questo:
num % 2 === 0

Quindi iniziamo a creare la nostra funzione JavaScript per verificare se un numero è un numero primo o meno:

function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

Ricorda che 2 È un numero primo

La funzione sopra tuttavia affermerà anche che 2 non è un numero primo, quindi dovremo riscrivere la nostra funzione. Possiamo anche occuparci di altri numeri interi che non sono numeri interi come 0 e numeri negativi.

function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

La parola chiave ‘return’ segnala un’uscita della funzione quando incontra un’istruzione che è vera. Se il numero è 2, la funzione smette di funzionare sulla seconda riga:

if (num === 2) return true;

Puoi trovare un ampio elenco di numeri primi noti qui per aiutarti a controllare la funzione.
Non tutti i numeri irregolari sono numeri primi

Questa funzione funziona bene per verificare se un numero è pari o meno, ma fallisce con numeri irregolari come 9 e 27 che non sono numeri primi.

Dovremo verificare se il parametro può essere diviso in altri fattori (ad eccezione di 1, se stesso e 2) senza lasciare un resto. Il numero 9 ad esempio può anche essere diviso per 3.

Lo facciamo facendo uso di un ciclo for in cui ad ogni iterazione, il parametro è diviso per un’altra variabile loop. Il ciclo continua a funzionare fino a quando non ci sono resti o non ci sono più variabili di ciclo disponibili.

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

La funzione mantiene il loop e il controllo dei resti. Ad ogni iterazione, l’argomento viene diviso per una nuova variabile loop e il resto viene controllato. Se il resto è 0, significa che l’argomento è completamente divisibile per un altro numero diverso da se stesso e non è un numero primo.

Nota a margine: Qual è la differenza tra un parametro e un argomento?
I parametri sono le variabili utilizzate come parte della definizione della funzione. Ad esempio il num in funzione isPrime(num) è il parametro.

Gli argomenti sono i valori passati alla funzione quando viene invocata. Ad esempio
il numero 9 in isPrime(9) è l’argomento.

Se c’è un resto, la funzione itera di nuovo fino a raggiungere il limite a

 i < num

Quando viene raggiunta l’iterazione finale e rimane ancora un resto, l’argomento è un numero primo e la funzione si arresta.
Terminiamo con una variabile loop che è un numero più piccolo del parametro perché non siamo interessati a fattori più grandi dell’argomento.

Una rapida dimostrazione

Dimostriamo questo con il numero primo di 5.

function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}

Primo ciclo:
1. i = 2 e 2 < 5, quindi continuiamo con il ciclo
2. 5% 2 dà un resto in modo da non uscire dal ciclo ma continuare con i++

Secondo ciclo:
1. i = 3 e 3 < 5, quindi continuiamo con il ciclo
2. 5% 3 dà un resto in modo da non uscire dal ciclo ma continuare con i++

Terzo ciclo:
1. i = 4 e 4 < 5, e abbiamo raggiunto la fine del ciclo perché 5 non è < di 5
2. 5% 4 dà un resto. Ciò significa che il numero 5 è un numero primo

Usando radici quadrate con numeri primi più grandi

I numeri primi si trasformano rapidamente in numeri enormi. Ciò significa che il nostro ciclo for continua a iterare dalla variabile di un ciclo alla successiva per numerose volte.

Possiamo abbreviare il processo utilizzando la radice quadrata di un parametro. Una radice quadrata di un numero intero è il numero che è stato moltiplicato da solo per creare un prodotto.

La radice quadrata di 81 è 9 perché 9 x 9 = 81.

Invece di iterare da 2 a 80 per verificare se ci sono resti rimasti o meno, possiamo semplicemente iterare fino a 9, la radice quadrata di 81.
9% 9 = 0, il che significa che 81 non è un numero primo.
Questo ha senso perché 9 x 9 sono fattori di 81, il che significa che non è conforme alla definizione di un numero primo — un numero che può essere diviso in parti uguali da solo e 1.

In JavaScript, puoi trovare la radice quadrata di un numero usando la matematica.Piazza. Lo scriviamo così:

Math.sqrt(num);

Usiamolo nella nostra funzione che controlla se un numero è un numero primo:

function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

Perché i numeri primi sono così utili?

In Contact, il libro di fantascienza di Carl Sagan, gli alieni inviano una lunga serie di numeri primi come prova che il loro messaggio proviene da una forza vitale intelligente. Non stiamo (ancora) comunicando con gli extraterrestri tramite numeri primi, ma li usiamo in vari modi proprio qui sul pianeta Terra.

Le cicale emergono sincronizzate in cicli esatti di numeri primi. I cicli irregolari significano che nessun predatore si è evoluto per vivere di questi insetti. Inoltre, il fatto che emergano tutti dal terreno a tempo aumenta le possibilità di sopravvivenza di un individuo.

Le schermate utilizzano numeri primi per definire le intensità di colore dei pixel. Sono anche utilizzati nella produzione di utensili per eliminare le armonie. Due ingranaggi che condividono un multiplo si impegnano gli stessi denti più e più volte che porta ad un modello di usura irregolare. Gli ingranaggi che hanno un numero primo di denti sui loro ingranaggi dureranno più a lungo.

I numeri primi sono comunque principalmente nella moderna sicurezza informatica. Non è così difficile trovare grandi numeri primi, ma è molto difficile da fattore grandi numeri in numeri primi.

È facile capire che 27 è 3 x 3 x 3 ma è molto più difficile scoprire che 2,244,354 è 2 x 3 x 7 x 53,437. E 2.244.354 non è nemmeno un numero così grande. Trovare i fattori primi è tecnicamente una questione di tempo, ma perché ci vorrà così tanto tempo diciamo che non può essere fatto.

I moderni algoritmi di crittografia utilizzano il fatto che non esiste ancora un computer che possa richiedere un numero super-grande e capire rapidamente quali numeri primi sono andati a realizzarlo.

Potresti fare shopping online o inviare un messaggio crittografato tramite un’app sul tuo telefono, ma da qualche parte, in qualche modo i numeri primi ti stanno aiutando a mantenere i tuoi segreti al sicuro.

Ecco altri tre link ad altri articoli di “Un algoritmo al giorno”:

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.