O método mais básico de verificar a primalidade de um número inteiro n é chamado divisão de teste. Essa rotina consiste em dividir n por cada número inteiro m maior que 1 e menor ou igual à raiz quadrada de n. Se o resultado de qualquer uma dessas divisões for um número inteiro, n não é um primo, caso contrário, é um primo. De fato, se for composto (com a e b ≠ 1), um dos fatores a ou b é necessariamente no máximo. Por exemplo, para, as divisões de teste são por m = 2, 3, 4, 5 e 6. Nenhum desses números divide 37, portanto 37 é primo. Essa rotina pode ser implementada com mais eficiência se for conhecida uma lista completa de números primos até então, as divisões de avaliação precisam ser verificadas apenas para os m que são primos. Por exemplo, para verificar a primalidade de 37, são necessárias apenas três divisões (m = 2, 3 e 5), considerando que 4 e 6 são compostos.
O que o número inteiro m deve ser menor ou igual ao executar a divisão de teste?
menor ou igual à raiz quadrada de n