XP is just a number PerlMonks

Re^2: Perl vs. Python for prime numbers

by danaj (Monk)
 on Jun 22, 2013 at 09:28 UTC ( #1040264=note: print w/ replies, xml ) Need Help??

in reply to Re: Perl vs. Python for prime numbers
in thread Perl vs. Python for prime numbers

We could save typing and electrons:

```use Math::Prime::Util qw/forprimes/;
forprimes { say } 1000;  # optionally takes range a,b
OK, it's cheating using modules. But it's easy, and it also uses a segmented sieve so should be efficient even with large values (e.g. list the primes between 10**18 and 10**18+100000), and works with bigints too.

Some Python ways to do this, all of which are *much* faster than the OP code when we want anything more than tiny values like 1000. There are probably even better ways.

Using sympy. Much slower than the Perl module:

```from sympy import sieve
for i in sieve.primerange(2,1000):
print i

using gmpy2 (only ~2x slower than the Perl module):

```import gmpy2
n = 2
while n <= 1000:
print n
n = gmpy2.next_prime(n)

Or some Python by hand that is very fast:

```from math import sqrt, ceil

def rwh_primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-a
+ll-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a list of primes, 2 <= p < n """
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1
+)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(
+i&1))/6-1)/k+1)
sieve[n/3-correction] = False
# If you want the count:  return 2 + sum(sieve)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve
+[i]]

for i in rwh_primes(1000):
print i

Comment on Re^2: Perl vs. Python for prime numbers

Create A New User
Node Status?
node history
Node Type: note [id://1040264]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (16)
As of 2015-08-03 19:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?