Conosci prima la definizione
Un numero primo è un numero intero maggiore di 1 con esattamente due divisori positivi: 1 e il numero stesso. I primi numeri primi sono 2, 3, 5, 7, 11 e 13. Il numero 1 non è né primo né composto, e 2 è l'unico primo pari.
Controlla solo fino alla radice quadrata
Per testare un intero positivo n, non è necessario provare tutti i numeri inferiori a n. Se n ha un fattore maggiore della radice quadrata, deve avere anche un fattore di corrispondenza minore della radice quadrata. Quindi è sufficiente testare i possibili divisori fino alla radice quadrata.
- Se il numero è inferiore a 2 non è primo.
- Controlla se è divisibile per 2. Se è pari e maggiore di 2, non è primo.
- Prova i divisori dispari da 3 fino alla radice quadrata. Se qualcuno si divide equamente, il numero è composto.
- Se nessuno divide equamente il numero è primo.
Esempio: 97 è primo?
La radice quadrata di 97 è poco meno di 10. Controlla i possibili divisori primi fino a quel punto: 2, 3, 5 e 7. Il numero non è divisibile per nessuno di essi, quindi 97 è primo.
Per 91, la verifica trova 7: 91 ÷ 7 = 13. Ciò è sufficiente per dimostrare che 91 è composto; non è necessario testare divisori più grandi.
Errori comuni
- Chiamare 1 primo. Un numero primo deve avere esattamente due divisori positivi, mentre 1 ne ha solo uno.
- Supponendo che ogni numero dispari sia primo. I compositi dispari come 9, 15, 21 e 91 hanno divisori dispari.
- Testare solo pochi piccoli divisori per un numero grande. Il controllo deve coprire ogni possibile divisore fino alla radice quadrata o utilizzare un algoritmo di primalità verificato.
UsefulVerse controlla i pratici input di numeri interi localmente nel tuo browser. Un risultato fondamentale è un controllo di divisibilità, non una prova di una chiave crittografica o un sostituto di un software specializzato di teoria dei numeri.