如何在PYTHON中查找素数 [英] How to find prime numbers in python

查看:75
本文介绍了如何在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
> 

这篇关于如何在PYTHON中查找素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆