파이썬으로 주어진 숫자가 Wagstaff 소수인지 확인하는 방법

Wagstaff 소수(Wagstaff Prime)란?

어떤 수 n이 주어졌을 때, 이 수가 Wagstaff 소수인지 판별해야 하는 경우가 있습니다. Wagstaff 소수는 다음과 같은 형태로 표현되는 소수를 말합니다.

n = (2^q + 1) / 3

여기서 q는 반드시 홀수인 소수(odd prime)여야 합니다.

예를 들어 입력값이 n = 683이라면 결과는 True가 됩니다. 683은 다음과 같이 표현할 수 있기 때문입니다.

683 = (2¹¹ + 1) / 3

이 경우 q = 11이며, 11은 홀수이면서 소수이므로 조건을 충족합니다.

해결 접근 방법

주어진 숫자가 Wagstaff 소수인지 확인하려면 다음 단계를 따릅니다.

• 먼저 해당 숫자 num이 소수인지 확인합니다.
• 다음으로 (num × 3 − 1)의 값이 2의 거듭제곱인지 확인합니다. 이는 곧 q가 존재하는지를 검사하는 것과 같습니다.
• 두 조건을 모두 만족하면 True를 반환하고, 하나라도 만족하지 않으면 False를 반환합니다.

예제 코드

아래 파이썬 구현 예제를 통해 더 잘 이해할 수 있습니다.

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def power_of_two(num):
    return num and not(num & (num - 1))

def solve(num):
    if isPrime(num) and power_of_two(num * 3 - 1):
        return True
    return False

n = 683
print(solve(n))

코드 설명

• isPrime(num): 2부터 num−1까지 나누어 떨어지는 수가 있는지 검사하여 소수 여부를 판별합니다.
• power_of_two(num): 비트 연산을 활용한 효율적인 기법으로, num이 0이 아니고 num & (num − 1)의 결과가 0이면 2의 거듭제곱임을 의미합니다.
• solve(num): 위 두 함수를 결합하여 num이 소수이면서 동시에 (num × 3 − 1)이 2의 거듭제곱인지 확인합니다.

입력

683

출력

True

이처럼 소수 판별 함수와 2의 거듭제곱 검사 함수를 함께 사용하면, 주어진 숫자가 Wagstaff 소수의 정의에 부합하는지 간단하고 효율적으로 확인할 수 있습니다.