如何在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)

但它不起作用。谁能帮帮我。感谢！

---

解决方案

您的示例count_primes()函数实际上都不算素数--它们只是打印奇数。让我们实现试验除法代码的工作版本，不使用令人困惑的布尔值和糟糕的算法，而是利用for循环上的else子句：

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评论的那样，筛选Eratosthenes是更好的方法。(+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
>