时间戳

首页 > 解决方案 > 计算素数的数量直到某个大值

python - 计算素数的数量直到某个大值

问题描述

我写了这个超级简单的python代码来计算素数的数量，直到某个大的值。问题在于1e+8程序需要花费大量时间这样的值，我想改进此代码以获得更快的结果和更好的性能。这是代码：

import math

def is_prime(num):
    if num%2 ==0 and num>2:
        return 0
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return 0
    return 1

def count_prime(num):
    ct=0;
    for i in range(2,num+1,1):
        if is_prime(i)==1:
            ct+=1
    return ct

标签： pythonprimes

解决方案

正如评论中所建议的，您可以开始改进您的 is_prime()函数。尝试其他算法，例如建议的筛子或Miller Rabin 测试。我在密码学研讨会期间实施了后者，这并不难。（注意：该算法是一种概率算法，但不要太在意）。这可能会为您的主要检查带来更好的时间复杂度。

在此之后，您可能会考虑多次运行您的count_prime()函数。在这里，您可以存储运行中的值，并在下一次开始时从这一点开始。

例子：

  1. 在第一次运行中，您计算​​ n = 5000的所有素数。你得到一些结果 = x 你将 x 存储为 5000。
  2. 在第二次运行中，您可能输入10.000作为您的指定输入。现在您不需要从 2 重新开始，但是您可以从存储的结果开始并从 5001 继续计算。结果相加然后是 10.000 的结果

推荐阅读