루카스-레머테스트

메르센소수

어느날 지식인에 메르센 소수를 판별하는 파이썬 프로그램이 필요하다는 질문이 올라왔다. 질문자는 대학생인걸까?

루카스-레머 테스트는 메르센소수(소수 p에 대하여 2^p - 1 도 소수인 경우)를 판별하는 알고리듬이다.

참고 : https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

아래코드는 해당 알고리듬을 파이썬으로 구현한 것이다. 소수 p를 받아서 메르센소수인지를 검사한다.

def is_mersenn_prime(p):
    if p == 2:
        return True
    mp = (1 << p) - 1
    s = 4
    for _ in range(0, p - 2):
        s = (s ** 2 - 2) % mp
    return s == 0