Check Prime Number
Un numero primo è un numero intero maggiore di 1 i cui unici divisori sono 1 e se stesso. Ti viene dato un intero positivo n. Restituisci true se n è primo e false altrimenti. Il numero 1 non è primo.
Funzione
- ninteger
- l'intero positivo da verificare
- Restituisceboolean
- true se n è primo, false altrimenti
Vincoli
1 ≤ n ≤ 231 - 1
Esempi
- Input
- n = 29
- Output
- true
- Spiegazione
- Nessuno tra
2,3,4e5divide29, e6 × 6 = 36supera già29, quindi non resta alcun divisore da trovare.29è primo.
- Input
- n = 1
- Output
- false
- Spiegazione
- Un numero primo ha esattamente due divisori,
1e se stesso.1ha un solo divisore, quindi la risposta èfalse.
- Input
- n = 91
- Output
- false
- Spiegazione
91sembra primo, ma7 × 13 = 91. Il divisore7salta fuori prima che la ricerca superi√91 ≈ 9.5.
+15 test nascosti all’invio
Per approfondire
Ogni numero primo maggiore di 3 ha la forma 6k-1 o 6k+1. Puoi usare questo fatto per testare solo un terzo dei divisori candidati?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Un numero primo non ha divisori tra
2en-1. Devi davvero verificare tutto quell’intervallo?Se
ddividen, anchen / dlo divide, e uno dei due è al massimo√n. Puoi fermarti quandod * dsuperan.Escludi prima
n < 2e i numeri pari diversi da2. Poi prova i divisori dispari a partire da3finchéd * d ≤ n, mantenendod * din un tipo a 64 bit.
Soluzione
La definizione dice di escludere ogni divisore da 2 a n-1, e per il più grande valore primo in input si tratta di oltre due miliardi di divisioni. I divisori si presentano in coppie il cui prodotto è n, e il più piccolo di ogni coppia è al massimo √n. Quindi cerchi solo fino a √n, al massimo circa 23,000 candidati dispari.
Prova ogni divisore
Corretto, ma non termina sui test più grandi
Intuizione
La definizione ti fornisce l’algoritmo. Un numero n ≥ 2 è primo quando nessuno tra 2, 3, ..., n-1 lo divide. Verifica ogni candidato d con n % d == 0 e restituisci false al primo che lo divide. Per 91 il ciclo prova da 2 a 6 e si ferma a 7.
Gestisci prima n < 2. Per n = 1 l’intervallo dei candidati è vuoto, quindi il ciclo non troverebbe mai un divisore e considererebbe 1 primo.
I numeri composti di solito si fermano presto, ma un numero primo supera ogni test, quindi il ciclo arriva fino alla fine. Per n = 2147483647, che è primo, si tratta di circa 2.1 × 10^9 divisioni, molte più di quante se ne possano fare in pochi secondi.
Algoritmo
- Se
n < 2, restituiscifalse. - Fai scorrere
dda2an-1. - Se
n % d == 0, restituiscifalse. - Dopo il ciclo, restituisci
true.
def isPrime(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return TrueDivisione per tentativi fino alla radice quadrata
Intuizione
I divisori si presentano a coppie. Se d divide n, anche n / d lo divide, e i due si moltiplicano dando n. Non possono essere entrambi maggiori di √n, perché in tal caso il loro prodotto sarebbe maggiore di n. Quindi, se n ha un divisore diverso da 1 e da sé stesso, ne ha uno che è al massimo √n. Per 91 la coppia è 7 e 13, e 7 ≤ 9.5. Se nessun numero fino a √n divide n, allora non lo divide nemmeno nessun numero maggiore.
Scrivi il limite come d * d ≤ n invece di chiamare una funzione di radice quadrata. Si rimane nell’ambito dei numeri interi, senza arrotondamenti. Il segno di uguale è importante: 49 = 7 × 7, e il suo unico divisore 7 si trova esattamente in √49.
Puoi anche saltare la metà dei candidati. Gestisci 2 a parte: un n pari è primo solo quando è 2. Dopodiché, un n dispari ha solo divisori dispari, quindi inizia da 3 e procedi a passi di 2. Per n = 2147483647 il ciclo ora viene eseguito circa 23,000 volte invece di 2.1 × 10^9.
Algoritmo
- Se
n < 2, restituiscifalse. - Se
nè pari, restituisci il risultato din == 2. - Inizializza
da3e ripeti il ciclo finchéd * d ≤ n, usando un tipo a 64 bit perd. - Se
n % d == 0, restituiscifalse. Altrimenti aggiungi2ad. - Dopo il ciclo, restituisci
true.
def isPrime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2 # 2 is the only even prime
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
Trappole e casi limite
L’idea sta in una riga. Gli errori si nascondono ai limiti: gli input più piccoli e l’ultimo divisore.
- Restituire
trueper1. Ha un solo divisore, non due, quindi non è primo. - Rifiutare
2perché è pari. Controllan == 2prima di escludere i numeri pari. - Eseguire il ciclo mentre
d * d < ninvece che con≤. I quadrati di numeri primi come9,49e2147117569 = 46337²vengono quindi considerati primi. - Overflow in
d * d. In uninta 32 bit,46341 × 46341 = 2147488281non rientra e diventa un numero negativo, quindi il test continua a essere superato e il ciclo prosegue ben oltre√n. Usa un tipo a 64 bit perd, oppure confrontad ≤ n / d. - Usare come limite il risultato in virgola mobile di
sqrte troncarlo. Undoubleè esatto per ogninin questo caso, ma per gli input a 64 bit l’arrotondamento può portare a un valore inferiore di uno rispetto alla radice effettiva e saltare l’unico divisore importante.d * d ≤ nnon comporta questo rischio.
Domande frequenti4
Qual è la complessità temporale della verifica della primalità di un numero?
La divisione per tentativi fino a √n richiede un tempo O(√n) e spazio O(1). Per n fino a 2^31-1 si tratta al massimo di circa 46,000 divisioni, o 23,000 se si saltano i divisori pari. Testare ogni divisore fino a n-1 è O(n), circa due miliardi di passaggi per l’input più grande.
Perché controlli solo i divisori fino alla radice quadrata di n?
I divisori si presentano in coppie d e n / d il cui prodotto è n. Se fossero entrambi maggiori di √n, il loro prodotto sarebbe maggiore di n. Quindi ogni coppia ha un elemento minore o uguale a √n e, se entro quel punto non compare alcun divisore, n è primo.
1 è un numero primo?
No. Un numero primo ha esattamente due divisori distinti, 1 e sé stesso, mentre 1 ne ha solo uno. Escludere 1 fa sì che la scomposizione in fattori primi di ogni numero intero sia unica. Ecco perché isPrime(1) restituisce false.
Esiste un modo più veloce per verificare se numeri molto grandi sono primi?
Per un numero a 32 bit, la divisione per tentativi fino a √n è abbastanza veloce. Per i numeri con decine di cifre, i programmi usano il test di Miller-Rabin, che verifica alcune potenze modulari invece di provare i divisori. Per elencare tutti i numeri primi fino a un limite, il crivello di Eratostene è più efficiente che testare ogni numero singolarmente.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def isPrime(n):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
n = 29
Atteso
true