遍历列表并找到质数并添加到另一个列表

Question

我想遍历 python 中的一个列表，检测素数，然后将它们添加到另一个列表中。

primes = []
nprimes = []
for j in range(0, len(arr)):
    num = arr[j] #my list with numbers to check 

    if num > 1:
        for k in range(2, num):
            if (num % k) == 0:
                nprimes.append(num)
                break
            else:
                primes.append(num)
               
    else:
        print(num, " can't be checked, because its smaller than 1")

我遇到的问题是总是添加非质数的数字。同样，一般来说，代码似乎无法正常工作。

Answer 1

如果 num % k == 0 是 false 你不能直接说它是 prime 你必须等待整个循环，所以用 for 循环移动 else，它将是没有遇到 break 的执行，这意味着它是素数

您可以直接迭代值 for num in arr
你可以在 sqrt(num) 处停止你的循环，在那之后你将找不到新的除数

for num in arr:
    if num > 1:
        for k in range(2, int(num ** 0.5) + 1):
            if num % k == 0:
                nprimes.append(num)
                break
        else:
            primes.append(num)
    else:
        print(num, " can't be checked, because its smaller than 1")

Answer 2

出于学习目的，让我们尝试一下不同的方法。首先，我建议您将您的试验除法代码移到它自己的谓词函数 is_prime() 中，即 returns True 或 False，这样它就可以独立于您的其余代码进行优化。

然后，我将 itertools.groupby 将列表分为素数序列和非素数序列，我们将它们拼接到适当的列表中：

def is_prime(number):
    if number < 2:
        return False

    if number % 2 == 0:
        return number == 2

    for divisor in range(3, int(number ** 0.5) + 1, 2):
        if number % divisor == 0:
            return False

    return True

if __name__ == "__main__":

    from random import sample
    from itertools import groupby

    array = sample(range(1, 100), 15)

    primes = []
    composites = []

    for are_prime, numbers in groupby(array, is_prime):
        if are_prime:
            primes.extend(numbers)
        else:
            composites.extend(numbers)

    print("Numbers:", array)
    print("Primes:", primes)
    print("Composites:", composites)

输出

% python3 test.py
Numbers: [91, 87, 10, 2, 11, 24, 21, 12, 46, 61, 15, 32, 57, 22, 5]
Primes: [2, 11, 61, 5]
Composites: [91, 87, 10, 24, 21, 12, 46, 15, 32, 57, 22]
%

有很多方法可以解决这个问题，其中很多都具有教育意义！

遍历列表并找到质数并添加到另一个列表

Iterate through list and find prime numbers and add to another list

python

arrays

primes

list

python-3.x