Il metodo più semplice per verificare la primarietà di un dato numero intero n è chiamato divisione di prova. Questa routine consiste nel dividere n per ogni numero intero m superiore a 1 e inferiore o uguale alla radice quadrata di n. Se il risultato di una di queste divisioni è un numero intero, allora n non è un primo, altrimenti è un primo. Infatti, se  è composto (con a e b. 1) allora uno dei fattori a o b è necessariamente al massimo. Ad esempio, le divisioni di prova sono ad esempio: m = 2,3,4,5 e 6. Nessuno di questi numeri divide 37, quindi 37 è la prima. Questa routine può essere implementata in modo più efficiente se si conosce un elenco completo di primes fino a : quando le divisioni di prova devono essere controllate solo per quelle che sono prime. Ad esempio, per verificare la primarietà di 37, sono necessarie solo tre divisioni (m = 2,3 e 5), dato che 4 e 6 sono composte.
Qual è il modo più elementare per testare la primarietà di un numero intero n?
divisione di prova divisione di prova divisione di prova divisione di prova