时间戳

首页 > 解决方案 > python 3素数错误答案产生为什么这段代码给我错误的素数，如9,21，.......？

python - python 3素数错误答案产生为什么这段代码给我错误的素数，如9,21，.......？

问题描述

primef = []
def i_prime(n) :
    count = 0
    for i in range ( 0, n ):
        for j in range ( 2, i ):
            if (not i % j == 0):
                yield i
                count += 1
            else:
                break


for i in i_prime(45):
    primef.append(i)
primefe = list(set(primef))
print(primefe)

标签： pythonyieldprime-factoring

解决方案

你的逻辑似乎有一些缺陷。你所做的基本上是一个奇数生成器（想想为什么）。由于这部分已经回答，这里有一些提示：

  1. 我不建议使用这种算法来生成素数，因为它效率低下。您也可以将所有产生的素数缓存在一个列表中，并且只检查该列表而不是 for j in range(2, i):.
  2. 通过利用数论中的一个事实，还有一种更有效的方法来生成素数，该事实表明所有大于 3 的素数都具有以下形式6k+1或6k+5其中 k 是整数，这对于实际目的而言是非负的（背后的解释相当简单）。这是我在解决 Project Euler 问题时编写的一段代码：
def is_prime(x: int) -> bool:
    if x <= 3:
        return x > 1
    elif x % 2 == 0 or x % 3 == 0:
        return False    
    
    i = 5
    while i*i <= x:
        if x % i == 0 or x % (i + 2) == 0:
            return False
        i = i + 6
    
    return True

这个素数检查器对我来说是一个有用的生成器，可以在 0.6 秒内找到第 10001 个素数（对于 Project Euler 问题）。

如果您有任何与此实施相关的问题，请向我提问。

推荐阅读