如何在 python 中找到质数

Question

我是 Python 的新手。我正在尝试计算给定范围内的素数。开发者分享的一些答案是这样的：

import math
def count_primes(num):
    out = []

    for i in range(3,num,2):
        if all(i%j!=0 for j in range(3,int(math.sqrt(i))+1,2)):
            out.append(i)

    print(out)

我写了一个这样的：

import math
def count_primes(num):
    out = []
    for i in range(3,num,2):
        for j in range(3, int(math.sqrt(i))+1,2):
            if i%j != 0:
                out.append(i)           
        print(out)

但它不起作用。有人可以帮帮我吗？赞赏！

Answer 1

像这样的东西应该有用。您必须设置一个变量，因为 15%9 != 0，输出 True。

import math
def count_primes(num):
    out = []
    for i in range(3,num,2):
        prime = True
        for j in range(3, int(math.sqrt(i))+1,2):
            if i%j == 0:
                prime = False
        if prime:
            out.append(i)
    print(out)
    
count_primes(15)

Answer 2

您的代码与其他代码不同的原因是因为它们使用了 all() 方法。看看我是如何使用 bools:

实现该方法的

import math
def count_primes(num):
    out = []
    for i in range(3,num,2):
        f = True
        for j in range(3,int(math.sqrt(i))+1,2):
            if i%j==0:
                f = False
                break
        if f:
            out.append(i)

    print(out)
    
count_primes(20)

输出：

[3, 5, 7, 11, 13, 17, 19]

Answer 3

你附加到模块的结果不等于零。但是，如果所有模都不等于零（您的代码中缺少 all 语句），则它只是质数。

Answer 4

您的示例 count_primes() 函数实际上都没有计算素数——它们只是打印奇数素数。让我们实现您的 trial division 代码的工作版本，不使用混淆的布尔值和错误的算法，而是利用 Python 的 else 子句 for 循环：

def collect_odd_primes(number):
    primes = []

    for candidate in range(3, number, 2):
        for divisor in range(3, int(candidate ** 0.5) + 1, 2):
            if candidate % divisor == 0:
                break
        else:  # no break
            primes.append(candidate)

    return primes

print(collect_odd_primes(40))

输出

> python3 test.py
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
>

正如@MarkRansom 评论的那样，埃拉托色尼筛法 是更好的选择。 (+1) 现在，让我们将代码转换为计算奇素数：

def count_odd_primes(number):
    count = 0

    for candidate in range(3, number, 2):
        for divisor in range(3, int(candidate ** 0.5) + 1, 2):
            if candidate % divisor == 0:
                break
        else:  # no break
            count += 1

    return count

print(count_odd_primes(40))

输出

> python3 test.py
11
>

Answer 5

根据您运行的 code-writing 程序，另一种方法（与此问题的其他答案相反）是写：

    n = int(input("Write an integer:"))
    m = 2

    if n == 1:
        print(n, "is a prime number!")

    if n == 2:
        print(n, "is not a prime number.")

    while n > m:
        if n % m == 0:
            m = m + 1
            print(n, "is not a prime number.")
            break

        if n > n % m > 0:
            m = m + 1
            print(n, "is a prime number!")
            break

它可能不是最有效的，但它可以很好地直接回答“x”是否是素数！

如何在 python 中找到质数

How to find prime numbers in python

python

algorithm

primes