Finding The Nth Prime Number Using Python

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_n

Solution 1:

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:

defprimes(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]]

Solution 2:

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:

defisprime(test):
    if test == 2: returnTrueif test < 2or test % 2 == 0: returnFalsereturnnotany(test % i == 0for i inrange(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

defisprime(test):
    if test == 2: returnTrueif test < 2or test % 2 == 0: returnFalsereturnnotany(test % i == 0for i inrange(3, int(sqrt(test)) + 1, 2))

test_num = 2
prime_count = 1while (prime_count< 1000): 

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

Solution 3:

This is a code I wrote for C++. But the mentality must be the same.

// This code was written by Mert Ener#include<time.h>#include<vector>#include<iostream>private: System::Void button1_Click_1(System::Object^  sender, 
                                          System::EventArgs^  e){ 
    usingnamespace std;
    UInt64 cloc = clock();
    long m = 1;
    long k = long::Parse(textBox1->Text)-2;   // The text you entered std::vector<long> p(1,2);                 //   for the nth primefor( long n = 0; n <= k; n++ ) {
        m += 2;
        for( long l = 1; l <= n; l++ ) {
            if (m % p[l] == 0) {
                m += 2;
                l=0;}}
        p.push_back(m);}
    textBox2->Text = p[k+1].ToString(); // The textbox for the result.
    MessageBox::Show("It took me " + (clock() - cloc).ToString() 
                     + " milliseconds to find your prime.");}

Solution 4:

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 inrange(7, 48, 2) ifall((x%y for y in islice( primes, 1, int(math.sqrt(x)) )))]
primes = primes + [x for x inrange(49, 2400, 2) ifall((x%y for y in islice( primes, 1, numchecks(x) )))]
primes = primes + [x for x inrange(2401, 1000000, 2) ifall((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 = 23527631if 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'