숫자 n이 있다고 가정합니다. n이 Wagstaff 소수인지 확인해야 합니다. 우리가 알고 있듯이 Wagstaff 소수는 다음 형식의 소수입니다.
여기서 q는 홀수 소수입니다.
따라서 입력이 n =683과 같으면 출력은 True가 됩니다. n은 다음과 같이 나타낼 수 있습니다.
여기에서 q =11입니다. 그리고 q는 홀수 소수입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- num이 소수이고 (num*3 - 1)도 소수이면
- 참 반환
- 거짓을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시 코드
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))
입력
683
출력
True