Algoritmo di controllo Python Prime
Controlla se un numero è primo usando Python. Esegui il nostro algoritmo interattivo per vedere un'iterazione matematica efficiente e una valutazione della radice.
Panoramica
Un numero primo è un intero positivo maggiore di 1 che non ha divisori positivi oltre a 1 e se stesso.
Il modo più inefficiente per verificare la presenza di un numero primo è ripetere fino al numero stesso. Un'ottimizzazione potente consiste nel verificare la divisibilità solo fino alla radice quadrata del numero.
Codice e output di esecuzione
Efficiente algoritmo di controllo dei primi che dimostra l'ottimizzazione O(sqrt(n)).
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}") 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> PrimeImplementazione passo dopo passo
- Crittografia e algoritmi di hashing
- Matematica didattica e teoria dei setacci
- Convalida backend per chiavi sicure
Domande frequenti
Perché controllare solo fino alla radice quadrata?
Se $n = a \times b$, allora almeno uno dei fattori ($a$ o $b$) deve essere minore o uguale alla radice quadrata di $n$. Pertanto, controllare più in alto è ridondante.
Argomenti correlati
Esegui e comprendi la sequenza di Fibonacci in Python. Questo esempio di codice interattivo mostra approcci iterativi e ricorsivi per generare numeri di Fibonacci.
Algoritmi di ordinamento PythonEsplora gli algoritmi di ordinamento di Python. Visualizza l'ordinamento a bolle e unisci l'ordinamento in modo nativo all'interno del contesto IDE del browser.