Question

ps1a version.
Hi, below is the version of answer to assignment 1.
Interesting to know your approach if it differs

Answer 1

# find 100th primer
primes=[2] #list of primes, staring from 2
qnum=3 #first number we put to 'question'
while (len(primes))<=1000 :

for jj in range(0,len(primes)):
bb = qnum % primes[jj] # generate remainder
if bb == 0: # if this remaider is zero ...
qnum=qnum+2 # ... then we can thow 'questioned' number away
else: # if qnum is not zero we start questioning this 'candidat' from the start
for kk in range (0,len(primes)): # and the point is not to miss divisors
zz = qnum % primes[kk]
if zz == 0:
qnum=qnum+2

#print qnum
primes.append(qnum) # add 'survived' number to list of primers
print "The 10th prime number is" , primes[9]
print "The 100th prime number is" , primes[99]
print "The 1000th prime number is" , primes[999]

Answer 2

pls use a code pasting site - http://dpaste.com/667060/
sure takes a long time ...
here is mine - http://dpaste.com/667067/

Answer 3

oh thanks

Answer 4

http://dpaste.com/hold/667068/

Answer 5

Your code is a lot faster indeed

Answer 6

Would you please explain idea behind
limit = int(candidate**.5)+2

Answer 7

i found somewhere that you only have to use divisors up to the the square root of the number that is being tested.

Answer 8

you can ask in math group to prove it for you :P

Answer 9

Yes you only need to check up to sqrt(x).

http://en.wikipedia.org/wiki/Primality_test

"The simplest primality test is as follows: Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

However, rather than testing all m up to n − 1, it is only necessary to test m up to \scriptstyle\sqrt n"

Answer 10

I know I may have overkilled it, but here's mine:

http://dpaste.com/hold/667157/

Answer 11

kimci, interesting solution, I reckon, it is fast, easy to understand and straightforward without mathematical tricks

Answer 12

Thank you all for your suggestions

Answer 13

Thanks! I haven't tried other bwCA's code, but I think his/hers might be a bit more optimized with the mathematical assumptions and python usage. This is my first time using Python so the syntax I use is what is used at the current lecture I'm at. Which I think I'm only a lecture ahead of Problem sets.