Numpy 埃氏筛筛选整数

埃氏筛筛选整数埃拉托斯特尼筛法简称埃氏筛,是一个筛选质数的算法。该算法用迭代的方式识别出已经找到的质数的倍数,能高效地筛选小于一千万的质数。让我们试着去寻找第10 001个质数。

具体步骤

首先必须要做的事情,就是创建一个自然数列表。

  1. 创建一个连续的整数列表。

使用NumPy中的arange函数创建数组。

a = numpy.arange(i, i + LIM, 2)
  1. 筛选出p的倍数。

不清楚埃拉托斯特尼本人是否希望我们这样实现算法,但确实可以这样做。把数组中能被p整除的元素移除,代码如下。

a = a[a % p != 0]

本章的完整代码如下:

import numpy

LIM = 10 ** 6
N = 10 ** 9
P = 10001
primes = []
p = 2

#通过列出前6个质数: 2、3、5、7、11和13,我们看到第6个质数是13。
#第10 001个质数是多少?

def check_primes(a, p):
    #2. 筛选出p的倍数
    a = a[a % p != 0]

    return a
for i in xrange(3, N, LIM):
    #1. 创建一个连续的整数列表
    a = numpy.arange(i, i + LIM, 2)

    while len(primes) 

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程