Problema
Un numero primo è maggiore di 1 ed è divisibile solo per 1 e per sé stesso. È sufficiente controllare i divisori fino alla radice quadrata di n.
Implementa is_prime(n).
Input
n: Il numero da verificare.
Output
Restituisci true se n è primo, altrimenti false.
Vincoli
-1.000 ≤ n ≤ 1.000.000.000.000
Esempi
Esempio 1
Input:
n = 29
Output atteso:
expected = TrueInput:
long long n = 29;
Output atteso:
bool expected = true;Input:
long n = 29;
Output atteso:
bool expected = true;Spiegazione
29 non ha divisori diversi da 1 e 29.
Esempio 2
Input:
n = 21
Output atteso:
expected = FalseInput:
long long n = 21;
Output atteso:
bool expected = false;Input:
long n = 21;
Output atteso:
bool expected = false;Spiegazione
21 = 3 × 7, quindi non è primo.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Gestisci prima i numeri sotto 2: non possono essere primi.
Suggerimento 2
Prova i divisori possibili solo fino alla radice quadrata del numero.
Suggerimento 3
Fai attenzione ai numeri pari e ai fattori ripetuti: basta un divisore per escludere la primalità.
Complessità attesa
tempo O(sqrt(n)), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.