Testing for the 1000th prime (7919)

[Dunkler]

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'

[Dunkler]

I found my answer

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

[griswolf]

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.

PS: Glad you found an answer.
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.

[Dunkler]

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!

[cyw]

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]

[Ashley_4]

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)