在python中打印素数系列

Question

我正在努力学习Python编程,我对此很陌生.

我在打印一系列素数从一到百时遇到了问题.我无法弄清楚我的代码是什么问题.

这是我写的; 它打印所有奇数而不是素数:

for num in range(1,101):
    for i in range(2,num):
        if (num%i==0):
            break
        else:
            print(num)
            break

Answer 1

你需要检查从2到n-1的所有数字(实际上是sqrt(n),但好吧,让它为n).如果n可以被任何数字整除,那么它不是素数.如果数字是素数,则打印它.

for num in range(2,101):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print num

你可以写更短更pythonic:

for num in range(2,101):
    if all(num%i!=0 for i in range(2,num)):
       print num

正如我已经说过的,最好检查除数不是从2到n-1,而是从2到sqrt(n):

import math
for num in range(2,101):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num

对于像101这样的小数字并不重要,但对于10**8,差异将非常大.

您可以通过将检查范围增加2来进一步改善它,从而只检查奇数.像这样:

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(2,int(math.sqrt(num))+1)):
       print num

编辑:

如在第一个循环中选择奇数,在第二个循环中不需要检查偶数,因此'i'值可以从3开始并跳过2.

import math
print 2
for num in range(3,101,2):
    if all(num%i!=0 for i in range(3,int(math.sqrt(num))+1, 2)):
        print num

Answer 2

break 结束它当前所处的循环.所以,你只是检查它是否可被2整除,给你所有的奇数.

for num in range(2,101):
    for i in range(2,num):
        if (num%i==0):
            break
    else:
        print(num)

话虽如此,有更好的方法在python中找到素数而不是这个.

for num in range(2,101):
    if is_prime(num):
        print(num)

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

Answer 3

希腊数学家Eratosthenes在两千多年前发明的一种更好的方法,不是试验分裂,而是通过反复抛出多个素数来筛选.

首先列出从2到最大期望素数的所有数字.然后重复取最小的未交叉数,并将其全部交叉掉; 保持未交叉的数字是素数.

例如,考虑小于30的数字.最初,2被识别为素数,然后4,6,8,10,12,14,16,18,20,22,24,26,28和30被划掉.接下来3被识别为素数,然后划掉6,9,12,15,18,21,24,27和30.下一个素数是5,所以10,15,20,25和30被划掉.等等.剩下的数字是素数:2,3,5,7,11,13,17,19,23和29.

def primes(n):
  sieve = [True] * (n+1)
  for p in range(2, n+1):
    if (sieve[p]):
      print p
      for i in range(p, n+1, p):
        sieve[i] = False

筛网的优化版本分别处理2并仅筛选奇数.此外,由于所有小于当前素数的平方的复合物被较小的素数划掉,内环可以从p ^ 2而不是p开始,外环可以在n的平方根处停止.我将保留优化版本供您使用.

Answer 4

我赞成不采用最佳解决方案并对其进行测试。以下是我为通过@ igor-chubin和@ user448810创建简单示例类所做的一些修改。首先，我要说的都是很棒的信息，谢谢大家。但是我必须感谢@ user448810的聪明解决方案，事实证明它是迄今为止（我测试过的）最快的解决方案。先生，真是太荣幸了！在所有示例中，我都将值100万（1,000,000）用作n。

请随时尝试代码。

祝好运！

Igor Chubin描述的方法1：

def primes_method1(n):
    out = list()
    for num in range(1, n+1):
        prime = True
        for i in range(2, num):
            if (num % i == 0):
                prime = False
        if prime:
            out.append(num)
    return out

基准：超过272+秒

Igor Chubin描述的方法2：

def primes_method2(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, num)):
            out.append(num)
    return out

基准： 73.3420000076秒

Igor Chubin描述的方法3：

def primes_method3(n):
    out = list()
    for num in range(1, n+1):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

基准： 11.3580000401秒

Igor Chubin描述的方法4：

def primes_method4(n):
    out = list()
    out.append(2)
    for num in range(3, n+1, 2):
        if all(num % i != 0 for i in range(2, int(num**.5 ) + 1)):
            out.append(num)
    return out

基准： 8.7009999752秒

如user448810所述的方法5（我认为这很聪明）：

def primes_method5(n):
    out = list()
    sieve = [True] * (n+1)
    for p in range(2, n+1):
        if (sieve[p]):
            out.append(p)
            for i in range(p, n+1, p):
                sieve[i] = False
    return out

基准： 1.12000012398秒

注意：上面列出的解决方案5（由user448810提出）是最快，最安静的创意和智慧。我喜欢它。多谢你们！！

编辑：哦，顺便说一句，我觉得没有必要为数值的平方根导入数学库，因为等效项就是（n **。5）。否则，我不会进行其他大量编辑，然后将值存储在输出数组中并由类返回。而且，将结果存储到文件中可能比冗长的效率更高，并且如果一次仅存储一个结果，则可以节省大量内存，但是由于磁盘写入，将花费更多时间。我认为总会有改进的空间。因此，希望这些代码有意义。