Número primo

Um número primo é um número natural maior que 1 que não pode ser formado pela multiplicação de outros dois naturais menores. Um número natural maior que 1 que não é primo é chamado de número composto. Por exemplo, 5 é primo porque as únicas maneiras de escrevê-lo como um produto, 1 × 5 ou 5 × 1, envolvem o próprio 5. No entanto, 4 é composto porque é um produto (2 × 2) no qual ambos os números são menores que 4. Os primos são centrais na teoria dos números devido ao teorema fundamental da aritmética: todo número natural maior que 1 ou é um primo, ou pode ser fatorado como um produto de primos de maneira única, salvo pela ordem dos fatores.

A propriedade de ser primo é chamada primalidade. Um método simples, mas lento, de verificar a primalidade de um número dado n, chamado de divisão por tentativa, testa se n é um múltiplo de qualquer inteiro entre 2 e . Algoritmos mais rápidos incluem o teste de primalidade de Miller–Rabin, que é rápido, mas tem uma pequena chance de erro, e o teste de primalidade AKS, que sempre produz a resposta correta em tempo polinomial, mas é muito lento para ser prático. Métodos particularmente rápidos estão disponíveis para números de formas especiais, como números de Mersenne. Em outubro de 2024, o maior número primo conhecido é um número primo de Mersenne com 41 024 320 algarismos.