Algoritmos Matemáticos para calcular números primos -Números de Mersenne

Algoritmo para testar a primalidade de números de Mersenne

Os números da forma Mⁿ = 2ⁿ-1 com n um número primo são chamados de números de Mersenne, a sua consideração deriva do estudo de números perfeitos (um número perfeito, é um número cujo resultado da soma dos seus divisores naturais é ele mesmo; por exemplo o número 6 tem como divisores 1,  2,  3 e 1+2+3=6, 28 tem como divisores 1, 2, 4, 7, 14 e 1+2+4+7+14=28) efectuado por Marin Mersenne.

Algoritmo:

Mⁿ =2ⁿ + 1 é um número primo se e só se Mⁿ divide Sn-2, com (Sk)k1, uma sucessão definida recursivamente por : 

S0= 4, Sk+1=Sk² -2.