Kiểm tra số có phải Wagstaff Prime trong Python

Wagstaff prime là số nguyên tố dạng (2^q + 1)/3 với q là số nguyên tố lẻ.

Ví dụ: n=683 → 683 = (2^11+1)/3, q=11 (nguyên tố lẻ) → True.

Điều kiện tương đương: n là nguyên tố VÀ (n*3 - 1) là lũy thừa của 2.

Thuật toán

• Kiểm tra n là nguyên tố.
• Kiểm tra (n*3 - 1) là lũy thừa của 2: x & (x-1) == 0.

Ví dụ code

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

Đầu vào

683

Đầu ra

True