Question

Compare thoughts on Ps1 solutions?

Answer 1

My stab:

# Initialize variables
prime_counter = 1
candidate = 3
divisor = 2

while prime_counter < 1000:
if candidate%divisor == 0: # for numbers that are not prime
candidate += 2
divisor = 2
elif divisor > (candidate/2): # for prime numbers
prime_counter += 1
if prime_counter == 1000:
print 'Prime #1000 =', candidate
candidate += 2
divisor = 2
else:
divisor += 1


It works but seems it could be tighter.

Answer 2

I did this some time ago and I'm rather happy with it, although I'm not sure if it was really necessary to print every prime number.

prime_candidate = 3
divisor = 2
prime_number = 2

print "2 is prime number 1"

while prime_number <= 1000:
while prime_candidate%divisor != 0:
divisor=divisor+1
if divisor == prime_candidate:
print prime_candidate, 'is prime number', prime_number
prime_candidate = prime_candidate+2
prime_number = prime_number+1
divisor=2
else:
prime_candidate = prime_candidate+2
divisor=2

Answer 3

Both of these work perfectly. I used lists to get the results working, but my code seems slower than these...I'll rework my original program now, to see if I can improve my code.

Answer 4

I did something very similar to fruiterian. The biggest block for me was figuring out how to reset the divisor after finding a prime. Part 2 of the PS was a piece of cake after getting the first part down.

Answer 5

I tried to use Fermat's little theorem but it doesnt seem to work :S It goes like this:

primes=[]
n = 0
for p in range (2,150000):
if n < 1000:
if (2**p-2) % p == 0:
primes.append(p)
n = len (primes)
print primes

Answer 6

here's what I did, seems to do the trick

x = 1
primes = [2]
logs = log(primes[0])
goal=1000
while len(primes) < goal:
x += 2
pcount = 0
for i in primes:
pcount += 1
if x % i == 0:
break
elif pcount == len(primes):
primes.append(x)
if len(primes) < goal:
logs += log(x)
break
print ("ratio", logs, " / ", primes[goal-1])

Answer 7

Milo, that's cool, and it works when I run it. Why did you choose the line:

elif pcount == len(primes):

I've never seen that used as the test of when to stop before.

Answer 8

i needed a way to divide the new candidate by every one of the existing prime numbers. Since the list f primes was always growing I needed a counter so this seemed to make sense :-S

Answer 9

Oh, that is cool! I actually hadn't noticed you were using the primes list--I just thought you were dividing each number by 0-len(primes). You could probably stop even earlier, too--when the current divisor is greater than sqrt(x).

Answer 10

OH! duh... I noticed in the P-set they mentioned that at somepoint you could probably stop checking the modulus but I didn't give it too much thought. If I feel ambitious maybe I'll rework my code later tonight :-)