Controlla se un numero è primo e trova tutti i primi in un intervallo
Un numero primo è un numero naturale maggiore di 1 che non ha divisori positivi diversi da 1 e se stesso. 2, 3, 5, 7, 11, 13... sono i primi numeri primi. Il teorema fondamentale dell'aritmetica afferma che ogni intero maggiore di 1 può essere espresso in modo univoco come prodotto di numeri primi.
Questo strumento verifica se un numero è primo, trova la sua fattorizzazione prima se è composto e lista i numeri primi in un intervallo dato. I numeri primi sono alla base della crittografia moderna — RSA si basa sulla difficoltà di scomporre grandi numeri nei loro fattori primi.
Per numeri piccoli (<10⁶): divisione di prova fino a √n. Per numeri medi: Miller-Rabin deterministico. Per numeri molto grandi: Miller-Rabin probabilistico. AKS (2002) è stato dimostrato polinomiale.
Sì. Euclide lo dimostrò intorno al 300 a.C.: supponiamo una lista finita di primi, moltiplichiamoli tutti e aggiungiamo 1 — questo numero è primo o divisibile per un primo non nella lista. Contraddizione.
Un algoritmo antico per trovare tutti i primi fino a un limite n. Segna tutti i multipli di ogni primo. I numeri non segnati rimanenti sono primi. Complessità: O(n log log n).
Un numero primo della forma 2ⁿ − 1. Esempi: 3, 7, 31, 127. GIMPS coordina il calcolo distribuito per trovare nuovi numeri primi di Mersenne.
Calcolatore percentuale · Calcolatore età · Differenza di date · Calcolatrice scientifica · Calcolatore BMI · Generatore Fibonacci