与えられた番号がPythonでEuclid番号であるかどうかを確認します

数nがあるとします。 nがユークリッド数であるかどうかを確認する必要があります。私たちが知っているように、ユークリッド数は整数であり、

n =P _n +1

ここで、は最初のn個の素数の積です。

したがって、入力がn =211のような場合、出力はTrueになります。nは

211 =（2×3×5×7）+1

これを解決するには、次の手順に従います-

• MAX：=10000
• primes：=新しいリスト
• 関数generate_all_primes（）を定義します。これには時間がかかります
• prime：=サイズMAXのリストとTrueで埋める
• x：=2
• x * x
• prime [x]がTrueの場合、
  • x * 2からMAXの範囲のiの場合、各ステップでxずつ更新します。
    • prime [i]：=False
  • x：=x + 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))

入力

211

出力

True