Thursday, January 17, 2008

Project Euler - Prime Generation

Project Euler - Mathematics/CS competition site (http://www.projecteuler.net)
I want to show an alternate way than S of E, currently, that I know of.
The space required is just the array of primes.
I used to perform the Seives (of Erasothenes) which is N * lg lg N, which is quite fast.
However, a better technique (in terms of space) is used in the following example.
This code will be python, and I will show the implementation below.
I can find the 10,001st prime number in under one second.

#! /usr/bin/python
# This program computes
# 10,001st prime.
# count of how many primes
nprimes = 1
# current value
n = 1
# current primes list with
# its value squared
primes = [ (2,4) ]
while nprimes < 10001:
# Gen all primes
n += 2
for prime, primeSquared in primes:
if n < sq:
primes.append((n, n**2))
nprimes += 1
if nprimes == 10001:
print n
break;
if n % prime == 0:
break;

The Sieve Of Erasothenes (S of E) follows (which is much faster for large inputs):

#!/usr/bin/python
# O(N lg lg N)
import Numeric
primes = [2]
N = 2000000
p = Numeric.ones(N,Numeric.Int)
n = 3
c = 1
while n < N:
if p[n] == 1:
c += 1
primes.append(n);
j = n + n;
while j < N:
p[j] = 0
j += n
n += 2

1 comment:

some pathetic coder said...

This might be O(N * K)
where N is the value you want to stop at.
and K is how many primes until you get to N.

Could re-write it as.
primes.add( new tuple(2,4) );
for (int i = 3; i <= N; i += 2) {
for (tuple X : primes) {
if (i < X.squared) {
primes.add( new tuple(i,i*i) );
break;
}
if (i % X.prime == 0)
break;
}
}