10001素数

Question

问题描述：

通过列出前六个素数: 2，3，5，7，11和13，我们可以看到第6素数是13。

10001素数是多少？

素数：

素数是一个大于1的整数，其唯一的因子是1和它本身。因子是一个整数，它可以被平均地分成另一个数。

例:前25个素数(所有小于100的素数)是: 2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97

最好的解决方案是使用未定义

Eratosthenes的

筛：

在数学中，Eratosthenes的筛子是一种古老的算法，用于求任何给定极限以下的所有素数。

它通过迭代地将每个素数的倍数(即，非素数)标记为复合(即，非素数)，从第一个素数2开始。

给定素数的倍数是从素数开始生成的数列，与素数相等的素数之间的常差。

这是筛子从使用试除法到顺序测试每个候选数被每个素数整除的关键区别。

一旦发现的每一个素数的所有倍数都被标记为复合，剩下的无标记数就是素数。

当n小于1000万左右时，Eratosthenes筛是寻找所有小于n的素数最有效的方法之一。

Eratosthenes的

筛(分步)：

1-创建从2到n的连续整数列表：(2，3，4，…，n)。

最初，设p等于2，最小素数。

3-通过计数p从2p到n的增量来枚举p的倍数，并在列表中标记它们(这将是2p、3p、4p、.；p本身不应该被标记)。

4-在列表中找出大于未标记的p的最小数。如果没有这样的号码，就停下来。否则，让p现在等于这个新的数字(这是下一个素数)，并从步骤3重复。

5-当算法终止时，列表中未标记的数字都是n以下的素数。

我的解决方案

这是我的解决方案用于使用Python的欧拉项目的问题7：

 def sieve_of_eratosthenes(n): 
  '''method for finding all primes up to 
     a given natural n.
  '''
    is_prime = [True]*n
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2,int(math.sqrt(n)+1)):  
        index = i*2
        while index < n:
            is_prime[index] = False
            index = index+i
    prime = []
    for i in range(n):
        if is_prime[i] == True:
            prime.append(i)
    return prime

如何改进我的代码？

Answer 1

初始改进

不要使用int(math.sqrt(n))。Python的整数可能非常大，math.sqrt(n)需要在计算平方根之前首先将整数转换为浮点值，这可能导致在n超过2^{53}时得到不准确的结果。虽然您可能还没有达到这个限制，但函数math.isqrt(n) (在Python3.8中引入)避免了对浮点的转换，而且实际上可以更短地输入。

你的时间循环..。

        index = i*2
        while index < n:
            is_prime[index] = False
            index = index+i

..。可以使用Python的range对象替换为for循环：

        for index in range(i * 2, n, i):
            is_prime[index] = False

这应该比while循环更快，因为循环条件和增量都是在range()对象内部处理的。

用于收集素数的最后一个for循环可以使用enumerate函数替换为列表理解：

    primes = [i for i, flag in enumerate(is_prime) if flag]

功能改进

2是唯一的偶数素数。它是值得的，当单独处理它，只有测试奇数在筛子中。

因为在筛子中只考虑了奇数素数，所以你可以将你的“划出”增量加倍到2p。

另外，把2p，3p，4p的倍数划掉，.效率低下，因为在前面的步骤中，p^2下面的所有奇数倍数都将被删除。

正如vnp所指出的，您错过了“步骤4”。你不需要把合成数的倍数划掉，因为它们已经被划掉了。

    is_prime = [False, True] * (n // 2)
    is_prime[1] = False
    is_prime[2] = True

    for i in range(3, math.isqrt(n) + 1, 2):
        if is_prime[i]:
            for index in range(i * i, n, 2 * i):
                is_prime[index] = False

工具更改

https://pypi.org/project/bitarray/

有一个叫做bitarray的模块可以安装。与使用list存储is_prime标志不同，bitarray可以将这些标志存储在一个长缓冲区的单个位中。这是一个显着的内存优化。

此外，使用bitarray进一步简化了将多个值交叉到片分配操作的过程：

import bitarray

...

    is_prime = bitarray.bitarray(n)
    is_prime.setall(False)
    is_prime[2] = True
    is_prime[3::2] = True

    ...

    for i in range(3, math.isqrt(n) + 1, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = False

    ...

Answer 2

代码没有实现第4步，在进入消除循环之前，必须测试is_prime[index]。是False，别费心了。

第三步是次优。p小于p^2的每一个倍数都有一个因子小于p，因此已经被标记为非素数。直接从p^2中消除是安全的。

这个观察还允许删除对math.sqrt的调用，该调用在这个问题中看起来非常不合适。