使用 Python 檢查給定數字是否為歐幾里得數

假設我們有一個數字 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 < MAX 時，執行以下操作：
  • 如果 prime[x] 為 True，則
    • 對於從 x * 2 到 MAX 的範圍內的 i（每次增加 x），執行以下操作：
      • prime[i] := False
    • x := x + 1
• 對於從 2 到 MAX - 1 的範圍內的 x，執行以下操作：
  • 如果 prime[x] 為 true，則
    • 將 x 插入 primes 的末尾
• 從主方法執行以下操作：
• generate_all_primes()
• mul := 1, i := 0
• 當 mul < n 時，執行以下操作：
  • mul := mul * primes[i]
  • 如果 mul + 1 與 n 相同，則
    • 返回 True
  • i := i + 1
• 返回 False

讓我們看看以下實現以更好地理解：

示例程式碼

線上演示

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

Arnab Chakraborty

更新於： 2021年1月16日

174 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習