Hey guys, I am new here and have found many answers to my problems from this website so I figured it was time to join.

Here's the deal: I have just started trying to learn Python through MIT's OpenCourseWare. I am currently on PS1a (Problem set 1a) and am having trouble figuring this one out. My assignment is to test all odd integers from 2 to the 1000th prime (which happens to be 7919) for primality. Now I can do this (more or less) using Fermat's algorithm for primes, but it gives me quite a few pseudo primes and prints out the wrong number as the 1000th prime. So, I am revising my code to try and find a solution WITHOUT writing a function to determine primality. I want to do this test with a FOR loop. Any help will be appreciated.

2 things to note:
1. I am not a student looking for help on homework
2. I ran a search on the site and was unable to locate what I needed to solve this problem without using an IsPrime function.

``````fpn = 1000 # establishing my variable

for i in range(1, int(fpn**.5)+1): # setting up loop to check only to the sqrt of max number
if (i/2)*2 != i: # testing only odd numbers
if fpn%i == 0: # This may be my problem. I am seeing what odd #'s return no remainder
print i, 'is prime'
else: print i, 'is not prime'``````

``````limit = 20
# 2 is the first prime number
plist = [2]
for n in range(3, limit):
for x in range(2, n):
if n % x == 0:
break
else:
# this else has to line up with the inner for, not the if
# implies that the loop fell through without finding a factor
#print n, 'is a prime number'  # test
plist.append(n)``````

Thanks to VegaSeat

They all use the Sieve of Eratosthenes one way or another. Here's one for future consideration that uses the `yield` keyword in a generator that always yields the next prime. On my mac, it found 10,000 primes in about 5 seconds, but took about 85 seconds to find 20,000. It found 7919 in .097 seconds:

``````def nextprime():
primes = [2,3,]
for p in primes:
yield p
while True:
status = True
p += 2
for pv in primes:
if 0 == p % pv:
status = False
break
if status:
primes.append(p)
yield p

if __name__ == "__main__":
import sys
num = int(sys.argv[1])
print("Showing %d-th prime"%num)
g = nextprime()
for i in range(num-1):
g.next()
print(g.next())``````

Notes:

• Lines 4 and 14 are where the function 'returns' a value. State is saved and the function is restarted immediately after the `yield` on the next() call
• Lines 6, 10, 12: Since we are in two loops, I need a status variable to keep track of when we found a non-prime.
• Line 16 allows this file to be used as either a module or a script. When running as a script the built-in variable __name__ has the value "__main__"
• Line 17: Normally an import function will be one of the first few lines in the file, but it is legal here, and since only needed when running as a script, I put it here.

PPS: Please hunt down the 'thread solved' link near the bottom of the page and mark this thread solved... unless you have a remaining question.

One thing I might add to this code for efficiency is in line:

5. for x in range(2, n): You can set the upper limit of x to the square root of n because you don't need to check for primality beyond a certain point.

so to do that it would look like this

``````limit = 7920
plist = [2] # 2 is the first prime number

for n in range(3, limit):
[B]for x in range(2, int(n**.5)+1):[/B]
if n % x == 0:
break
else:
# this else has to line up with the inner for, not the if
# implies that the loop fell through without finding a factor
plist.append(n)

print "prime list  =", plist
print "list length =", len(plist)
print "last prime  =", plist[-1]``````

just my .02 cents... makes things a little snappier!

``````ans=1
count=1
test=()
primes=()
while count<1000:
ans=ans+1
for i in range(1,ans+1):
if ans%i==0:
test=test+(i,)
if len(test)<=2:
primes=primes+(ans,)
count=len(primes)
test=()
print primes[-1]``````

Greetings! I have also been working on the MIT opencourseware P-Set 1. A lot of the formulas above I have not learned yet, but for the problem set, I wrote a program that will tell you the nth prime you want. Here is my strategy:

``````y = 3
order_prime = 2

requested_prime = int(input("What prime would you like to know? "))

if requested_prime == 1:
print (2)

if requested_prime - int(requested_prime)!= 0 or requested_prime < 1:
requested_prime = int(input("Want to try that again? Positive integers only, please! "))

else:
requested_prime = int(requested_prime)

if order_prime == requested_prime:
print (y)

else:
while order_prime != requested_prime:

y = y + 2

odd_number = 3

while y%odd_number != 0 and odd_number <= y:

odd_number = odd_number + 2

if y <= odd_number:

order_prime = order_prime + 1

print (y)
``````