Finding the nth prime number using Python

Question

When I run this code, even for just counting to the 10th prime number (instead of 1000) I get a skewed/jacked output--all "not prime" titles for my is_composite variable, my test_num is giving me prime and composite numbers, and my prime_count is off

Some of the answers that developers have shared use functions and the math import--that's something we haven't yet covered. I am not trying to get the most efficient answer; I am just trying to write workable python code to understand the basics of looping.

---

  # test a prime by diving number by previous sequence of number(s) (% == 0).  Do this by
  # counting up from 1 all the way to 1000.

test_num = 2 #these are the numbers that are being tested for primality
is_composite = 'not prime' # will be counted by prime_count
prime_count = 0 #count the number of primes


while (prime_count<10): #counts number primes and make sures that loop stops after the 1000th prime (here: I am just running it to the tenth for quick testing)


 test_num = test_num + 1   # starts with two, tested for primality and counted if so
 x = test_num - 1  #denominator for prime equation

 while (x>2):   
  if test_num%(x) == 0:
   is_composite = 'not prime'
  else: 
   prime_count = prime_count + 1 
  x = x - 1 


  print is_composite
  print test_num
  print prime_count 

Answer 1

First of all, from the vague description of your prime checking algorithm, it appears that you are checking every number up to the number that you are testing for primality. However, in reality you are only required to test up to the square root of that number. A further optimization would be to remove all even numbers apart from two (you can do this by incrementing by twos from one and testing 2 separately), you end up with:

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

Then all you have to do is iterate through the numbers from 2 upwards checking if they are prime and adding one to your counter if they are. When you reach 1000 stop and output the number being passed to the isprime function.

Of course there are other more efficient methods, I personally prefer the Sieve of Atkin. But it would be up to you to implement that, my algorithm will serve your purposes.

Edit: I noticed your comment that 'nothing is returning/happening' that would be due to the inefficiency of your algorithm, if you wait long enough you will get an answer. However, I do notice that you have no print statement in the code you provided, I'm hoping the code which your running has one.

from math import sqrt

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

test_num = 2
prime_count = 1

while (prime_count< 1000): 

 test_num = test_num + 1  

 if (isprime(test_num)):
     prime_count += 1

print test_num

Answer 2

See the hints given by MIT for your assignment. I quote them below:

1. Initialize some state variables

2. Generate all (odd) integers > 1 as candidates to be prime

3. For each candidate integer, test whether it is prime

   3.1. One easy way to do this is to test whether any other integer > 1 evenly divides the candidate with 0 remainder. To do this, you can use modular arithmetic, for example, the expression a%b returns the remainder after dividing the integer a by the integer b.

   3.2. You might think about which integers you need to check as divisors – certainly you don’t need to go beyond the candidate you are checking, but how much sooner can you stop checking?

4. If the candidate is prime, print out some information so you know where you are in the computation, and update the state variables

5. Stop when you reach some appropriate end condition. In formulating this condition, don’t forget that your program did not generate the first prime (2).

It could look like this:

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

Answer 3

This code below generates a list of primes upto 1 million. Using that list, you can test for primes < 1 Trillion in a reasonably fast way. This runs in a pretty fast time for 10-12 digit primes.

import math
from itertools import islice
# number of primes below the square root of x
# works well when x is large (x > 20 and much larger)
numchecks = lambda x: int((math.sqrt(x))/(math.log(math.sqrt(x)) - 1.084)) + 1

primes = [2,3,5]
primes = primes + [x for x in range(7, 48, 2) if all((x%y for y in islice( primes, 1, int(math.sqrt(x)) )))]
primes = primes + [x for x in range(49, 2400, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]
primes = primes + [x for x in range(2401, 1000000, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]

You can increase the number of saved primes by extending the process above, but the program will take a long time (but one time only process).

In your code, you can test if 'test_num' is prime using the following...

test_num = 23527631
if test_num<100:
    checks = int(math.sqrt(test_num))
else:
    checks = numchecks(test_num)

isPrime = all(test_num%x for x in islice(primes, 0, checks))
print 'The number is', 'prime' if isPrime else 'not prime'
print 'Tested in', checks, 'divisions'