Python Program: Prime Number

A whole number $n > 1$ is a prime number if it is divisible only by 1 and itself. The number 2 is a prime number because it is divisible only by 1 and itself. The number 3 is also a prime number as the only two integers dividing it are 1 and itself. And so are 5, 7, 11, 13, 17, ...

Here, we will write a simple prime number program in Python.

The primality test we consider here is mainly based on the trial division method. We will elaborate this method with examples in the following paragraphs.

Consider the number 60. Below we list all its integer divisors:

2, 3, 4, 5, 6, 10, 12, 15, 20, 30

Expressing it by factors,

60 = 2 x 30, 3 x 20, 4 x 15, 5 x 12, 6 x 10, 10 x 6, 12 x 5, 15 x 4, 20 x 3, 30 x 2

Note that after the divisor 6 the factors are merely a repeat in the reverse order as the first divisor is simply the dividend of a previous divisor. And 6 is less than or equal to $\sqrt{60} \approx 7.74$. In this way, we actually just need to do divisibility tests from $2$ till $\sqrt{n}$.

Now take another number 29. As deduced in the previous paragraph, we need only test with divisors less than or equal-to $\sqrt{29} \approx 5.386$. These numbers are 2, 3, 4 and 5. But again, if an even number divides the number $n$, then so does 2. Which means, all even divisors after 2 are redundant and can be eliminated. So 4 is unnecessary. Now this redundancy is applicable not just for even numbers or multiples of 2, it applies the same for multiples of 3 as well. And next for multiples of 5, then 7, and so on. So, basically, we need to be dividing only with primes less than or equal to $\sqrt{n}$. This is the method of trial division. This leaves us with just 2, 3 and 5. And we find that 29 is not divisible by 2 or 3 or 5, so it must be prime.

But collecting a set of primes $\sqrt{n}$ to divide a number $n$ is another program in itself, which we will not be pursuing here in our program.

We import the math module to make use of the sqrt() function.

				
				import math;

				n = int(input("n = "))

				flag = 0
				i = 2

				while i <= math.sqrt(n):
					if n%i == 0:
						flag = 1
					i+=1

				if(flag == 1):
					print(n, " is not a prime number")
				else:
					print(n, " is a prime number")


				print()
				
			

We run the above program for the numbers 73 and 97, and we find them both to be primes.