Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def primeSieve (primes = None, start = 0, length = 4096):
- # primes = primes or [ (3, 3) ]
- primes = primes or []
- sieve = [ 0 ] * length
- # Sieve known / existing primes
- last_prime = 3
- for i, (p, x) in enumerate(primes):
- while x < (start + length) * 2 + 1:
- sieve[(x - 1 - start) / 2] = 1
- x += p * 2
- primes[i] = (p, x)
- if p > last_prime:
- last_prime = p
- # Apply sieve forwards until we hit length
- for i in range((last_prime - 1 - start) / 2, length, 1):
- if sieve[i] == 0:
- p = i * 2 + start + 1
- x = p
- while x < (start + length) * 2 + 1:
- sieve[(x - 1 - start) / 2] = 1
- x += p * 2
- primes += [(p, x)]
- return primes
- def naivePrimes (N):
- primes = []
- for i in range(3, N * 2 + 1, 2):
- isPrime = True
- for p in primes:
- if i % p == 0:
- isPrime = False
- break
- if isPrime:
- primes += [i]
- return primes
- if __name__ == '__main__':
- SIEVE_SIZE = 60000
- NTH_PRIME = 10001
- import time
- t0 = time.time()
- first = lambda (a,b): a
- primes = map(first, primeSieve(None, 0, SIEVE_SIZE))
- t1 = time.time()
- print(primes)
- t2 = time.time()
- print("\nSIEVE:")
- print("Generated %d primes (first: %s, last: %s)"%(len(primes), primes[0], primes[-1]))
- print("Generated in %s seconds"%(t1 - t0))
- print("Printed in %s seconds"%(t2 - t1))
- print("%dth prime is %s"%(NTH_PRIME, primes[NTH_PRIME]))
- t0 = time.time()
- primes2 = naivePrimes(SIEVE_SIZE)
- t1 = time.time()
- print("\nNAIVE:")
- print("Generated %d primes (first: %s, last: %s)"%(len(primes2), primes2[0], primes2[-1]))
- print("Generated in %s seconds"%(t1 - t0))
- print("%dth prime is %s"%(NTH_PRIME, primes2[NTH_PRIME]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement