素数 PYTHON:

Question

我在编写一个程序来查找第 n 个数字的所有素数并打印它们时遇到了困难。这是我到目前为止所拥有的，如果有人可以帮助并解释我做错了什么，我将不胜感激：

def isPrime (n):
   primeList = [2]
    for i in range (3, n):
        if n%2 == 0 or n%3 == 0:
            break
        else:
            primeList.append(i)
            break
    return (primeList)

Answer 1

你必须检查你的数字是否能被迄今为止添加的所有素数整除，而不是检查它是否能被 2 和 3 整除。

def isPrime (n):
   primeList = [2]
   for i in range (3, n):
       isPrime = True
       for prime in primeList:
           if i % prime == 0:
               isPrime = False
               break
       if isPrime:
           primeList.append(i)
   return primeList

Answer 2

是的，您需要一种足够的方法来确定一个数字是否是素数。按照目前的情况，您只需检查该数字是否能被 2 和 3 整除，而不是 5、7 或更高的值。您可以通过循环遍历小于当前数字的数字来检查这一点：

    for i in range(3, n):
        for j in range(2, i):
            if i % j == 0:
                break
            primeList.append(i) # only runs if loop not broken

    return primeList

如果你愿意，我会让你优化它

Answer 3

fermets 公式是最简单的一种，但由于使用幂计算，可能会存在内存效率问题（除平方根法和 AKS 法外）

def prime(n):
    # you can replace the 2 with any coprime number
    if (n < 2): return False;
    if 2**(n-1)%(n) == 1: return True;
    return False

def range_primes(r):
    p = [2];
    for i in range(1, r):
        if prime(i) == True:
            p.append(i);
    return p;