ตรวจสอบว่าเลขเป็น Wagstaff Prime หรือไม่ด้วย Python

Wagstaff Prime: จำนวนเฉพาะรูปแบบ (2^q + 1)/3 โดย q เป็น Odd Prime

ตัวอย่าง

n = 683 → True เพราะ 683 = (2^11 + 1)/3, q=11 (Odd Prime)

อัลกอริทึม

1. ตรวจสอบ n เป็น Prime
2. ตรวจสอบ (n*3 - 1) เป็น Power of 2 (เพราะ n = (2^q+1)/3 → 3n-1 = 2^q)
3. ทั้งคู่ True → Wagstaff Prime

โค้ดตัวอย่าง

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))

Input / Output

Input: 683
Output: True