Várias fórmulas já foram propostas para gerar números primos arbitrariamente grandes: Fermat, por exemplo, conjecturou que todo número da forma 22n + 1fosse primo, o que foi desmentido por Euler ( 225 + 1 é composto). Apesar dos esforços, não se conhece nenhuma fórmula simples para gerar primos arbitrariamente grandes, e a maioria dos matemáticos acredita que não existe uma fórmula deste tipo.
Existem entretanto algumas fórmulas que geram famílias interessantes de primos. A fórmula deste tipo que mais nos interessa é Mp = 2p -1, os chamados números de Mersenne. Quando Mp é primo, dizemos que Mp é um primo de Mersenne. Parte da razão pela qual números desta forma são interessantes é que apesar de Mp nem sempre ser primo é relativamente fácil testar para um dado expoente p, mesmo bastante grande, se Mp é primo ou composto. Em grande parte por este motivo os seis maiores primos conhecidos hoje são primos de Mersenne e ao longo da história o maior primo conhecido quase sempre foi um primo de Mersenne(ver tabelas).