in reply to Perl vs. Python for prime numbers

This is a message from "saving electrons for better purposes.org"

my @perfectly_well_known_prime_number_under_thousand = (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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 1
+57, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
+233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311,
+ 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397
+, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 47
+9, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 5
+77, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 
+659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751,
+ 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853
+, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 94
+7, 953, 967, 971, 977, 983, 991, 997);

foreach (@perfectly_well_known_prime_number_under_thousand){
print $_," is a prime number and everybody knows it. I will not spend 
+CPU cycles in vain\n"}

[download]

(I bet that this is faster...) ;-)

Replies are listed 'Best First'.
Re^2: Perl vs. Python for prime numbers
by danaj (Friar) on Jun 22, 2013 at 09:28 UTC
    We could save typing and electrons: 
    use Math::Prime::Util qw/forprimes/;
forprimes { say } 1000;  # optionally takes range a,b

    [download]
    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

    [download]

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

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

    [download]

    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

    [download]
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom