Compare thoughts on Ps1 solutions?
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.
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
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.
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.
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
here's what I did, seems to do the trick x = 1 primes =  logs = log(primes) 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])
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.
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
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).
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 :-)
Join our real-time social learning platform and learn together with your friends!