루카스-레머테스트

메르센소수

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

루카스-레머 테스트는 메르센소수(소수 $p$에 대하여 $2^p – 1$ 도 소수인 경우)를 검사하는 방법이다.

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

아래코드는 해당 알고리듬을 파이썬으로 구현했다.

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

(입력 p는 소수이며, 2^p – 1 의 값이 소수이면 True를 리턴한다.)