Un numero primo e un numero naturale maggiore di 1 che sia divisibile solamente per 1 e per se stesso. Il piu piccolo numero primo e 2; tutti gli altri sono dispari, in quanto ogni numero pari e divisibile per 2. Nel passato 1 era a volte considerato un numero primo, oggi tuttavia si preferisce escluderlo. Un metodo per verificare se un numero n e primo discende direttamente dalla definizione, controllare che non sia divisibile a nessun numero minore di n o, in modo piu efficiente, da nessun primo minore di n. Un antico algoritmo che evita le divisioni e il crivello di Eratostene che determina l'insieme dei primi minori o uguali ad n. Per far cio, l'algoritmo parte dall'insieme dei numeri naturali compresi tra 2 ed n, ed elimina i multipli dei numeri primi individuati in precedenza.