파이썬에서 주어진 숫자가 유클리드 숫자인지 확인하십시오.

<시간/>

숫자 n이 있다고 가정합니다. n이 유클리드 수인지 확인해야 합니다. 우리가 알고 있듯이 유클리드 수는

로 나타낼 수 있는 정수입니다.

n=P_n +1

여기서 처음 n개의 소수의 곱입니다.

따라서 입력이 n =211과 같으면 출력은 True가 됩니다. n은

로 나타낼 수 있습니다.

211=(2×3×5×7)+1

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

최대 :=10000
primes :=새 목록
generate_all_primes() 함수를 정의합니다. 소요 시간
prime :=MAX 크기 목록 및 True로 채우기
x :=2
동안 x * x
prime[x]가 True이면
- x * 2 ~ MAX 범위의 i에 대해 x만큼 각 단계에서 업데이트합니다.
  - prime[i] :=거짓
- x :=x + 1

2에서 MAX - 1 사이의 x에 대해 다음을 수행합니다.

prime[x]가 참이면
- 소수 끝에 x 삽입

기본 방법에서 다음을 수행합니다.

generate_all_primes()

물 :=1, 나는 :=0

mul

mul :=mul * 소수[i]

mul + 1이 n과 같으면

참 반환

나는 :=나는 + 1

거짓을 반환

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

예시 코드

MAX = 10000
primes = []
 
def generate_all_primes():
   prime = [True] * MAX
 
   x = 2
   while x * x < MAX :
      if prime[x] == True:
         for i in range(x * 2, MAX, x):
           prime[i] = False
      x += 1

   for x in range(2, MAX):
      if prime[x]:
         primes.append(x)

def solve(n):
   generate_all_primes()
   mul = 1
   i = 0
 
   while mul < n :
      mul = mul * primes[i]
      if mul + 1 == n:
         return True
      i += 1
   return False

n = 211
print(solve(n))

입력

출력

True