质数查找器

Question

我正在尝试制作一个找质数的程序，为了节省计算时间，我希望一旦找到一个不是1也不是这个数字本身的因数，就能停止循环。现在这个功能是可以工作的，但它完全忽略了我的条件判断。我哪里做错了呢？

def prime(number):
    oldnum = number
    factor = 1
    while number > 1:
        factor += 1
        while number % factor == 0:
            if 1< factor < oldnum:
                return 0 # is not prime
                print("yay")
                break
            number //= factor
    return 1 #prime!

Answer 1

只需使用埃拉托斯特尼筛法。这是一种古老且经过验证的方法，用来找出质数 :)

Answer 2

关于提高性能的小建议，你只需要检查从 2 到 num 的平方根 sqrt(num) 之间的数字，而不是从 2 到 num 的所有数字。

Answer 3

你的代码永远不会到达 return 1 这一行（顺便说一下，这里应该是 return True），原因有两个：

• 你的 break 语句只会跳出内层的 while 循环。
• 而且这个 break 语句根本不会被执行，因为你在它之前就已经 return 0 了。

其实，你的内层 while 循环应该改成 if，因为你并没有做什么需要循环的事情。

如果你做了这个修改（并去掉那些永远也到不了的代码），那么代码就“能工作”了（除了 prime(1) 返回 True 这个错误的结果），不过这仍然是一个非常低效的找质数的方法。

def prime(number):
    oldnum = number
    factor = 1
    while number > 1:
        factor += 1
        if number % factor == 0:
            if 1 < factor < oldnum:
                return False # is not prime
            number //= factor
    return True # is prime!