使用 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习