숫자가 Python에서 원시 소수인지 확인하십시오.

<시간/>

숫자 n이 있다고 가정하면 n이 원시 소수인지 여부를 확인해야 합니다. 숫자는 pN# + 1 또는 pN# – 1 형식의 소수일 때 원시 소수라고 합니다. 여기서 pN#은 처음 N 소수의 곱이 되는 pN의 원시를 나타냅니다.

따라서 입력이 29와 같으면 29가 N=3인 경우 pN - 1 형식의 원시 소수이고 원시가 2*3*5 =30이고 30-1 =29이므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

최대 :=100000
prime :=크기가 MAX이고 True로 채워진 목록
arr :=새 목록
SieveOfEratosthenes() 함수를 정의합니다. 소요 시간
범위 2에서 int((MAX)의 제곱근) + 1까지의 pri에 대해, do
- prime[pri]가 True와 같으면
  - pri * 2 ~ MAX 범위의 i에 대해 각 단계에서 pri씩 업데이트, do
    - prime[i] :=거짓
범위 2에서 MAX까지의 경우 다음을 수행합니다.
- prime[pri]가 0이 아니면
  - arr 끝에 pri 삽입
메인 방법에서 다음을 수행하십시오. -
prime[n]이 0이면
- 거짓을 반환
제품 :=1, 나는 :=0
제품
제품 :=제품 * ar[i]
product + 1이 n과 같거나 product - 1이 n과 같으면
- 참 반환
나는 :=나는 + 1

거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from math import sqrt
MAX = 100000
prime = [True] * MAX
arr = []
def SieveOfEratosthenes() :
   for pri in range(2, int(sqrt(MAX)) + 1) :
      if prime[pri] == True :
         for i in range(pri * 2 , MAX, pri) :
            prime[i] = False
   for pri in range(2, MAX) :
      if prime[pri] :
         arr.append(pri)
def check_primorial_prime(n) :
   if not prime[n] :
      return False
   product, i = 1, 0
   while product < n :
      product *= arr[i]
      if product + 1 == n or product - 1 == n :
         return True
      i += 1
   return False
SieveOfEratosthenes()
n = 29
print(check_primorial_prime(n))

입력

출력

True