|
+ Search |
|
Jun 16th, 2000 10:48
Dan Gindikin, unknown unknown, http://www.inetarena.com/~pdx4d/ocn/numeracy2.html#sieve
initial answer: import re for n in range(2, 1000): if not re.match('(11+)\\1+$', '1'*n): print n and then again: While the above submission is an interesting application of regular expressions, it's not really the way to get a list of primes. Below is primes.py, taken from the standard distribution that is faster by a factor of 10-20: primesuspects = range(3,1000,2) ptr = 0 while ptr < len(primesuspects): val = primesuspects[ptr] for i in primesuspects[ptr+1:]: if not i % val: primesuspects.remove(i) ptr = ptr + 1 print primesuspects -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- The standard way to find primes below a certain number is to use the Sieve of Erastosthenes: def erastosthenes(n): "A prime number sieve, returns list of primes <= n" sieve = [0, 0] + [1] * n # [0 0 1 1 1...] prime = 2 # initial prime while prime**2 <= n: for i in range(prime**2, n+1, prime): sieve[i] = 0 # step through sieve by prime prime = prime+1 + sieve[prime+1:].index(1) # get next prime # filter grabs corresponding range members only when seive = 1 return filter(lambda i, sieve=sieve: sieve[i], range(n+1)) it is about 2 to 3 times faster than the solution above for n=1000. The difference in running time becomes significantly more pronounced for larger n.