Calculating the Nth Prime Number

Introduction

I recently began a self-paced course of learning Python. This is a big departure from all my other articles which are written in C++ with MFC. I wanted to get current in programming and Python is a great way for me to do that. I am still very new to Python. One of the sessions had me create a prime number generator. I was not satisfied with the code that was demonstrated so I set myself to optimize it.

This script calculates the N^th prime number. During the course work, Python classes were demonstrated and I am very comfortable with this topic as it is very similar to C++. One optimization I made was to skip checking of even numbers. Even numbers can never be a prime number by definition because they are always divisible by 2.

What is a prime number? A prime number is a number that is greater than 1 and only divisible by 1 or itself. The number 2 is prime because it is greater than 1 and only divisible by 2. 3, 5, and 7 are also prime numbers for the same reason.

Background

The online training course that I am using is the URL of https://www.youtube.com/watch?v=Vxw1b8f_yts.

Using the Code

To use the code, create a CPrime object with the N^th prime number that is desired. The basic idea of calculating a prime number is to loop from 2 to the number-1. The script accomplishes this using an outer loop and an inner loop. The outer loop counts how many prime numbers have been discovered and exits when the Nth prime number is discovered. The inner loop is initialized with two numbers. The first number is "i" and represents a number to be checked for being a prime. The second number is a counter from 2 upto the prime minus 1. To test for prime-ness, the second counter is modulus divided into the first. If there is a remainder, then this number is a candidate for being prime and the counter is increased and then rechecked. If there is no remainder, then the number is not a candidate for being prime. The first optimization breaks out of the inner loop when a number is rejected. The second optimization ensures that only odd numbers are tested.

For example:

# Calculate the 10th prime number
MyPrime = CPrime(10)
print(MyPrime.GetPrime())

The entire script:

"""
This script calculates a prime number
"""

# Base class
class CCalculate:
    def __init__(self):
        pass

    def IsEven(self, num):
        if num % 2 == 0:
            return True
        return False

# Derived class
class CPrime(CCalculate):
    def __init__(self, nthPrime):
        self.nthPrime = nthPrime

    # return the nth Prime number
    def GetPrime(self):

        nthPrime = self.nthPrime
        counter = 0
        i = 2

        while counter < nthPrime:
            bPrime = True
            j = 2

            while j < i:
                if i % j == 0:
                    bPrime = False
                    break
                else:
                    j = j + 1
            
            if bPrime is True:
                counter = counter + 1

            # Increase the number
            i = i + 1

            # if the next iteration does not finish the loop or
            # it is an even number, then increase it to make it odd
            if counter < nthPrime and self.IsEven(i) is True:
                i = i + 1

        return i - 1

Points of Interest

I learned about Python classes which have some subtle differences than C++ classes. Python derived classes constructor needs to be manually called for base class initialization.

History

• 3^rd February, 2018 - Script submission