Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes

Question

I've got this, and it works. It just takes a large amount of time for numbers 100000+ I'm looking to cut it down so that it can calculate the 1,000,000th prime in less than 3 minutes. I've set it so that our number (chk) is only having numbers (odds) being divided into it, to check for divisibility, up to the square root of chk. The program is set to find the nth prime number up to the 1000000th. Thanks.

goal=int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))  #how many primes we need to find

if goal>1000000:         #closes the program if the number doesn't fit the parameters
    exit()
if goal==1:              #takes care of the first prime, which is 2
    print("2")
if goal==2:              #and then the second, which is 3
    print("3")

chk=5         #the next odd number after 3, which is already taken care of above
primes=2    #the number of primes recorded, after counting 2 and 3.
x=0         #the last recorded prime number
while primes<goal: 
    if  chk<9:     #if the number is odd and below 9....
        primes+=1  #it's prime
        x=chk      #record that number
        chk+=2     #and check the next odd number

    else:              #if it's =>9......
        odds=3         #check to see if it's divisible by the smallest odd number
        sqrtk=chk**.5  #all the way up to the square root of chk

        while odds<sqrtk or odds==sqrtk:   #if at any time...
            if chk%odds==0:                #...chk is divisible by this odd number....
                chk+=2                     #then raise the value of chk to the next odd number
                break                      #and start the check from the beginning with next k
            else:            #if not...
                odds+=2         #check to see if it's divisible by the next odd number. 

        if odds>sqrtk:             #if chk isn't divisible by any odds up to the square root of chk     
                primes+=1        #we have a prime number
                x=chk         #record that number
                chk+=2        #check the next odd number to see if it's prime
                odds=3         #and reset odds back to 3 to use it next time


if primes==goal:                  #once we've reached the desired amount of prime numbers
    print("The",goal,"prime number is:",x)      #print that prime number

Answer 1

A better way would be to generate a list of prime numbers as you go along, and check if the number can be divided by a number of that list

list = [ ]

while primes < goal: 
  found = false
  for n in list
    if chk % n = 0
      # is prime
      found = true
      break
  if not found
    list.append(chk)

To generate the list in less time, try using a different programming language. Below is the program in C++, which can generate the first 1.000.000 in under 10 seconds (depending on what you're using).

To do so, a few math assumptions were considered: 1) Only check odd numbers 2) Only check against numbers lower than the square root of the current number

Also, a few C optimizations were done: 1) Define the array size at first. By doing so, we don't have to deal with the costly operations of reallocating memory 2) Use "register" to speed up time critical processing blocks 3) pre-compute sqrt(chk) to speed up

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include <iostream>
#include <math.h>


#define NUMBERS 1000000


using namespace std;


main(int argc, char **argv)
{
  unsigned *list = (unsigned*)malloc(NUMBERS * sizeof(unsigned) );
  if(!list)
    exit(1);

  list[0] = 2;

  register unsigned primes = 1;
  unsigned goal = NUMBERS;
  unsigned chk = 3;

  clock_t tStart = clock();

  bool found;

  while(primes < goal) {
    found = false;
    register unsigned sq = sqrt(chk);
    for(register unsigned i = 1 ; i < primes ; i++) {
      if(list[i] > sq)
        break;
      if(chk % list[i] == 0) {
        found = true;
        break;
      }
    }
    if(!found) {
      list[primes++] = chk;
   }

    chk += 2;
  }


  printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

  for(int i = 0 ; i < primes ; i++)
    cout << list[i] << "  ;  ";
  cout << endl << endl;

  free(list);
}

The same program in python took 126s to run, under the 180s.

import sys
import os
import datetime
import csv
import time
import math


list = [ 2 ]

goal = 1000000
primes = 1

chk = 3

start = time.time()

while primes < goal:
  found = False
  sq = math.sqrt(chk)
  for n in list:
    if sq < n:
      break
    if chk % n == 0:
      # is prime
      found = True
      break
  if not found:
    list.append(chk)
    primes = primes + 1

  chk = chk + 2

end = time.time()
print end - start

Answer 2

I've (almost) completely revised the code by adding all prime numbers to a list and by only checking to see if those numbers divide evenly into the number we're checking. It runs much faster but still does not compute 1,000,000 in under 3 minutes.

Also, I want to write this without having to import any libraries. Time is only there for me to test, of course, time.

import time
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
start = time.time()
if goal > 1000000:
    exit()

if goal > 4:
    lst = [2, 3, 5, 7]
    chk = 11
    primes = 4
    while primes < goal:
        for n in lst:
            if n > chk**.5:
                lst.append(chk)
                primes += 1
                break
            if chk % n == 0:
                break
        chk += 2

    else:
        print("The", str(goal), "prime number is:", str(chk - 2))

else:
    if goal == 1:
        print("2")
    if goal == 2:
        print("3")
    if goal == 3:
        print("5")
    if goal == 4:
        print("7")
elapsed = (time.time() - start)
print(elapsed)

Answer 3

If you only care about the first million primes, the easiest solution is to pre-compute the list of the first million primes, using the Sieve of Eratosthenes, then index into the list to find the nth prime. Here's a simple Sieve of Eratosthenes:

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

The millionth prime is 15485863, so pre-compute and store the first million primes:

ps = primes(15485863)

Then you can easily look up the nth prime:

def nthPrime(n):
    return ps[n-1]

Here are some examples:

>>> nthPrime(1)
2
>>> nthPrime(10000)
104729
>>> nthPrime(1000000)
15485863

Pre-computing the first million primes takes only a few seconds, and looking up the nth prime is instant.