isPrime 函数（列表 + % 运算符）

Question

我正在尝试获取一个函数来确定 N 是否为质数。我是 Python 的新手，我知道这可能不是解决这个问题的最有效方法，但这是我的尝试

def is_prime(N):
    k = []                                     #Creates a new list k
    for i in range(2,N):                       #For each i from 2 -> N
        r = N%i                                # r is the remainder of N % i
        k.append(r)                            # appends each remainder r to list k

        if (i == N-1):                         #Once index equals N-1, print list k
            print(k)           

        #For each element j in list k, check if each element in list k is 0
            for j in range (len(k)):        
                if k[j] != 0:             <---PROBLEM
                    return True
                else:
                    return False
print(is_prime(15))

我的逻辑是，当一个数能被1和它本身整除，并且不能被2到N-1之间的任何其他数整除时，它就是质数。在上面的代码中，我在比较列表 k 中每个元素的值时遇到 问题。我想判断是否每个元素的值k[j] == 0。如果每个元素k[j] != 0 and N%1 == 0 and N%N == 0，则为质数！

关于如何解决这个问题有什么想法吗？请参考下面的 link 以可视化我的代码！ http://goo.gl/IVIRz7

Answer 1

我建议如下解决：

def is_prime(n):
    i = 2
    while (i * i <= n):
        if (n % i == 0):
            return False
        i += 1
    return True

此代码适用于 n >= 2。

Answer 2

以上答案可行，但我想我应该解释一下您的逻辑错误。您的英语推理是合理的，因为如果 [2,N-1] 之间的任何数字均除 N，则您找到了 non-prime 个数字。

    for j in range (len(k)):        
        if k[j] != 0:             
            return True
        else:
            return False

这个循环实际上检查的是k中的第一个数是否为0。如果它不为零，则该数不会整除 N（注意这并不意味着其他数会整除 n），因此该数仍然可能是质数，但前提是对于剩余的潜在除数，余数不为零。换句话说，你可以 return Falseas 当你看到余数为 0 时，但你只能 return True 仅当 all 除数具有非零余数时。

固定：

        for j in range (len(k)):        
            if k[j] == 0:
                return False
            return True

return True 语句只有在我们设法在没有 returning False 的情况下完成整个循环时才会执行。

Answer 3

import math

def is_prime(n):
    i = 3
    while (i <= math.sqrt(n)):
        if (n % i == 0):
            return False
        i += 2
    return True

这是最好的。上面的每个人都提到了它的变化。

isPrime 函数（列表 + % 运算符）

isPrime function (list + % operator)

python

algorithm

primes

python-3.x