Since primes require so much computing power, I tried to close down the number of candidates and tests as much as I could. To do that, I did three things:
Since 2 is the first prime, generated only odd number candidates.
Stored the primes and used a slice based on the prime nearest 1/3 of the candidate value as test divisors. (Since all the even numbers are eliminated, 1/3 becomes the upper limit.)
Used the break keyword to exit the loop as soon as a candidate number was weeded out.
It runs pretty fast; here are the stats:
Total candidates tested: 3959
Total tests: 203,514
Average tests per candidate: 51
# Initialize state variables.
primes = [2]
count = 1
test_slice = primes[0:]
# Do this until we have 1000 primes
while len(primes) < 1000:
# Increment counter by 2. (Eliminates all divisible by 2.)
count += 2
# Set prime switch true.
is_prime = True
# Loop through the testing slice.
for prime in test_slice:
# Check to see if count is prime.
if count % prime == 0:
# Not a prime, set switch to false.
is_prime = False
# If divisible by 3, figure new test slice upper limit.
if prime == 3:
# Get the divisor limit.
divisor_limit = count / 3
# Check to see if it's in the prime array.
# (If divisor_limit is a power of 3, it won't be.)
if divisor_limit in primes:
# If it's a prime, find its index and add 1.
i = 1 + primes.index(divisor_limit)
# set the new test slice range from 1 to i.
test_slice = primes[1:i]
# Don't waste any more time on this number.
break
# Check the switch; if it's still true...
if is_prime:
#...count is prime. Add it to the primes array.
primes.append(count)
# This is only for the first loop.
if count == 3:
test_slice = [count]
# print
ordinal = str(len(primes)) + 'th'
print 'The', ordinal, 'prime is', count
I'd love to see if I could improve on that, but I'm really out of time this week.
![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
branchandroot
no subject
Date: 2010-01-17 11:45 pm (UTC)Since primes require so much computing power, I tried to close down the number of candidates and tests as much as I could. To do that, I did three things:
breakkeyword to exit the loop as soon as a candidate number was weeded out.It runs pretty fast; here are the stats:
# Initialize state variables. primes = [2] count = 1 test_slice = primes[0:] # Do this until we have 1000 primes while len(primes) < 1000: # Increment counter by 2. (Eliminates all divisible by 2.) count += 2 # Set prime switch true. is_prime = True # Loop through the testing slice. for prime in test_slice: # Check to see if count is prime. if count % prime == 0: # Not a prime, set switch to false. is_prime = False # If divisible by 3, figure new test slice upper limit. if prime == 3: # Get the divisor limit. divisor_limit = count / 3 # Check to see if it's in the prime array. # (If divisor_limit is a power of 3, it won't be.) if divisor_limit in primes: # If it's a prime, find its index and add 1. i = 1 + primes.index(divisor_limit) # set the new test slice range from 1 to i. test_slice = primes[1:i] # Don't waste any more time on this number. break # Check the switch; if it's still true... if is_prime: #...count is prime. Add it to the primes array. primes.append(count) # This is only for the first loop. if count == 3: test_slice = [count] # print ordinal = str(len(primes)) + 'th' print 'The', ordinal, 'prime is', countI'd love to see if I could improve on that, but I'm really out of time this week.