素数模块 [英] Prime number module

问题描述

是否有一个python模块，其中包含使用prime

数字的函数？我主要需要一个返回第N个素数的函数和

，它返回多少个素数小于N，但是一个素数

测试者也会很好。我正在处理10 ^ 6-10 ^ 8范围内的数字

所以它必须要相当高效


Dag

Is there a python module that includes functions for working with prime
numbers? I mainly need A function that returns the Nth prime number and
that returns how many prime numbers are less than N, but a prime number
tester would also be nice. I''m dealing with numbers in the 10^6-10^8 range
so it would have to fairly efficient

Dag

推荐答案

Dag写道：

Dag wrote:

是否有一个包含处理主要数字的函数的python模块？我主要需要一个返回第N个素数的函数和
，它返回多少素数小于N，但素数值测试器也会很好。我正在处理10 ^ 6-10 ^ 8
范围内的数字，所以它必须相当有效


gmpy对于这类事情非常有用，但它给出的原语

你是完全不同的 - is_prime来检查一个数字是否为素数，并且

next_prime以获得大于给定数字的最小素数。


你必须在此基础上构建自己的缓存，以避免重复

计算，如果你需要，例如，有多少质数是< N'QUOT;对于几个不同的N值;而且我甚至不确定gmpy'的原语是否适合这个（例如，与某种筛选相比）。

无论如何，所有这些警告，这里是一个示例函数：


import gmpy


def primes_upto（N）：

count = 0

prime = gmpy.mpz（1）

while prime< N：

prime = prime.next_prime（）

count + = 1

返回计数


并将其保存在pri.py中，这是我在时间上衡量的：


[alex @ lancelot python2.3]

Is there a python module that includes functions for working with prime
numbers? I mainly need A function that returns the Nth prime number and
that returns how many prime numbers are less than N, but a prime number
tester would also be nice. I''m dealing with numbers in the 10^6-10^8
range so it would have to fairly efficient
gmpy is pretty good for this sort of thing, but the primitives it gives
you are quite different -- is_prime to check if a number is prime, and
next_prime to get the smallest prime number larger than a given number.

You''d have to build your own caching on top of this to avoid repeating
computation if you need, e.g., "how many primes are < N" for several
different values of N; and I''m not even sure that gmpy''s primitives are
optimal for this (compared with, for example, some kind of sieving).
Anyway, with all of these caveats, here''s an example function:

import gmpy

def primes_upto(N):
count = 0
prime = gmpy.mpz(1)
while prime < N:
prime = prime.next_prime()
count += 1
return count

and having saved it in pri.py, here''s what I measure in terms of time:

[alex@lancelot python2.3]

python timeit.py -s''import pri'' - s''M = 1000 * 1000''

\''pri.primes_upto（M）''

python timeit.py -s ''import pri'' -s ''M=1000*1000''
\ ''pri.primes_upto(M)''

10循环，最好3：每循环2.76e + 06 usec

[alex @ lancelot python2.3]

10 loops, best of 3: 2.76e+06 usec per loop
[alex@lancelot python2.3]

python timeit.py -s''import pri''-s

''M = 2 * 1000 * 1000''''pri.primes_upto（M）''

10循环，最佳3：4.03e + 06 usec每循环


即2.76秒，素数高达1,000,000 - 约4秒

为素数高达2,000,000。 （这是我老好可靠的Athlon

Linux机器，现在大约30个月了，即使在新的时候也没有最高速度 - 我肯定是其中之一今天的典型个人电脑可能比这要少2或3美元b $ b倍，当然）。如果我在生产中使用这种b $ b计算，我会预先计算一些感兴趣的典型N的计数，并且仅生成和我认为，在
窄带中计算素数;但是如果你的申请没有更好的建议就很难提出建议。

Alex

python timeit.py -s ''import pri'' -s
''M=2*1000*1000'' ''pri.primes_upto(M)''
10 loops, best of 3: 4.03e+06 usec per loop

i.e., 2.76 seconds for primes up to 1,000,000 -- about 4 seconds
for primes up to 2,000,000. (This is on my good old trusty Athlon
Linux machine, about 30 months old now and not top-speed even when
new -- I''m sure one of today''s typical PC''s might take 2 or 3
times less than this, of course). If I was to use this kind of
computation "in production", I''d pre-compute the counts for some
typical N of interest and only generate and count primes in a
narrow band, I think; but it''s hard to suggest anything without a
better idea of your application.
Alex

这篇关于素数模块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！