Prime Number Program in Python

Last Updated on May 23, 2023 by Prepbytes

Prime numbers, the building blocks of the number system, have captivated mathematicians and computer scientists for centuries. These unique integers, divisible only by themselves and 1, play a fundamental role in various fields, including cryptography, number theory, and algorithm design. In this article, we delve into the implementation of a prime number program in Python, exploring the intricacies of identifying and generating prime numbers efficiently.

Throughout this article, we will unravel the key concepts and techniques involved in creating a prime number program in Python. We will discuss the fundamental properties of prime numbers, such as divisibility rules and prime factorization, to build a strong foundation for our program. Additionally, we will explore various efficient algorithms, such as the Sieve of Eratosthenes and the primality testing methods, to generate and verify prime numbers.

What are Prime Numbers?

Prime numbers are those that can only be divided by one (1) and by the original number. One outstanding example is the number 7, which consists just of the number 7 and the number 1. However, due to the presence of factors 2 and 3 in addition to factors 1 and 6, the number 6 is not a prime.

Some examples of prime numbers are 3,5,7,11,13,17,19,23, etc.

Non-prime numbers are referred to as composite numbers. But in mathematics, 1 is neither a prime number nor a composite number.

The smallest prime number.

The smallest prime number is 2, which. This is true since 1 is neither a prime nor a composite. Two is the first number after 1 that can only be divided by itself. Consequently, 2 is the smallest prime number.

Facts about Prime Number

Now let’s examine some useful information regarding prime numbers that you might find fascinating.

• Two is the only even prime number. This is because all other even integers, excluding 1 and the number itself, will also be divisible by 2.
• Only 2 and 3 are consecutive prime numbers. Such a pair is later missing.
• The number five is the only prime number that finishes in five. Any number after that with an even number ending in 5 will not be a prime number since it would likewise divide evenly by 5.
• After 2 and 3, every prime number has a 6n+1 or 6n-1 form.

Now that we are sufficiently knowledgeable on prime numbers, let us now move to the prime number program in Python.

Prime Number Program in Python

The problem formulation is thus quite straightforward. We are required to determine whether or not a particular number is a prime number. When given 7, for example, we will print "YES," however when given 10, we will print "NO."

So let’s examine the procedure in greater depth.

Method 1: Complete Factorization Prime Number Program in Python

So, we are aware that the only numbers that can be divided by one are the prime numbers and the number itself. We also know that each integer can be divided by one and by itself. There is no need to check that, so.

So, the negation approach is as follows. This means that rather than verifying or demonstrating that the number is a prime, we will instead attempt to demonstrate that it is not a prime (composite or 1). The number will be presumed to be a prime number if we are unable to disprove its primality.

So, we can follow the following algorithm for prime number in Python.

Algorithm for Prime Number in Python

• Check if the input number (N) is 1. If it is 1, it is neither prime nor composite. Still, it is not prime so we will print “NO”
• Else, iterate from 2 to N-1 and check if any number is able to divide the number N completely i.e. if any number from 2 to N-1 is a factor of N. If we find even one number that is a factor of N, N will not be a prime number as we would have a number apart from 1 and N that divides N completely. So, in this case, also, print “NO”
• Finally, if we have iterated from 2 to N-1 and have not found any factor of N, this means that N is only divisible by 1 and N itself. So, it is a prime number. Hence, print “YES”

Now that we have understood this procedure, let us write the code for the same.

Program for Complete Prime Factorization for finding Prime Numbers in Python

Prime number program in python 1

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2,n):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

Output

Prime

Time Complexity: The time complexity of this method is O(N) as we are traversing almost N numbers in case the number is prime.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

Method 2: Half Factorization Prime Number Program in Python

We may easily determine whether a given number is a prime number by iterating from 2 to N-1, as we saw. However, this strategy is not very optimized if we are given a large number as input.

We can comprehend that we don’t need to check till N-1 if we think about it thoroughly. N-1 cannot, of course, divide N. What then ought to be the endpoint?

A number is divided by two if it is even. As a result, its factor will also be its half. Additionally, we cannot assume that a number’s component will be its half if it is odd. There will, however, be at least one other component before its halfway point.

So, we may say that iterating from 2 to N/2 allows us to determine whether a number is a prime number or not. The number will be non-prime if there is a factor between 2 and N/2, otherwise it will be prime.

Code Implementation For Prime Number Program in Python

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2, n//2 + 1):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

Output

Prime

Time Complexity: Well, the time complexity remains the same i.e. O(N). However, we are iterating approximately just half as compared to before since we are going till N/2.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

Therefore, with the procedure described above, we have cut the number of iterations in half. Can we create a prime number program in Python with fewer asymptotic time complexity and iterations as well? So let’s examine that approach.

Method 3: Square Root Method Prime Number Program in Python

As we observed with the prior approach, we were able to cut the number of iterations in half. The time complexity is unchanged, though. Mathematical reasoning was used to justify cutting the iterations in half.

We also have a different mathematical rationale that will further cut down on iterations and temporal complexity. Use two composite numbers here. One of them ought to be a perfect square, whereas the other shouldn’t. Say we have the two integers 40 (which is not a perfect square) and 36 (which is a perfect square). Below is a list of these numbers’ factors.

So, can you find anything specific in these 2 factorizations?

The image above shows that the upper half and lower half of factorizations are mirror images of each other.

The square root factor is not mirrored and is located in the middle of perfect squares. The remaining components, however, are reflected.

Why does this matter? This means that there will always be at least one factor on or before the square root of a composite number, whether it be a perfect square or not. This is so because the factors above and below the square root are simply mirrored versions of one another.

Therefore, to determine if a number is a prime number or not, we look up its factors on or below its square root. The number is not prime if there is a factor; else, it is prime.

Let’s write the code for the procedure now that we have a better understanding of it.

Program for Square Root Method to identify a Prime Number in Python

m=0
flag=0
n = 11
if(n == 1):
  flag = 1
  print("Not Prime")
for i in range(2, n**(1//2) + 1):
  if(n % i == 0):
      print("Not Prime")
      flag=1
      break  
  
if (flag==0):
  print("Prime")

Output

Prime

Time Complexity: The time complexity of this solution is root N i.e. O(√N). This is because we are traversing just √N numbers.

Space Complexity (Auxiliary Space): Since we have not used any extra space, the auxiliary space is O(1).

These three techniques can be used to determine whether a given number is a prime number or not.

What would you do if we asked you to print all the prime numbers in a range? For example, we might give you the low and high values and ask you to publish every prime number between them. Therefore, we can apply the same technique as demonstrated below to find a prime number. We just apply a loop from low to high, and if a prime number is found, we print it. The corresponding code is displayed below.

Program to print Prime Numbers in a Range

lower = 90
upper = 150

print("Prime numbers between", lower, "and", upper, "are:")

for num in range(lower, upper + 1):
   # all prime numbers are greater than 1
   if num > 1:
       for i in range(2, num):
           if (num % i) == 0:
               break
       else:
           print(num)

Output

Prime numbers between 90 and 150 are:
97
101
103
107
109
113
127
131
137
139
149

Conclusion
In conclusion, the exploration of prime number programs in Python has provided us with a deeper understanding of prime numbers and their applications in various computational problems. Through this article, we have examined three different approaches for identifying prime numbers and an additional approach for generating prime numbers within a given range. By leveraging the power of Python’s syntax and libraries, we have unlocked the potential to efficiently tackle prime number-related challenges.

By understanding and implementing these different approaches, we have acquired a versatile toolkit for working with prime numbers in Python. Whether we need to verify if a single number is prime, generate a list of primes, or test large numbers for primality, Python offers a range of techniques to tackle these challenges efficiently.

FAQ related to Prime Number Program in Python

Q1: Why are prime numbers important?
Ans. Prime numbers play a crucial role in various fields such as cryptography, number theory, and algorithm design. They serve as the building blocks for many mathematical concepts and algorithms. Prime numbers are also used in encryption algorithms to ensure secure communication and in generating random numbers.

Q2: How can I check if a number is prime in Python?
Ans. There are multiple approaches to check if a number is prime in Python. Some commonly used methods include the trial division method (dividing the number by all integers up to its square root), the Sieve of Eratosthenes algorithm (generating all primes up to a given limit), and probabilistic primality testing algorithms like the Miller-Rabin test.

Q3: Can you explain the Sieve of Eratosthenes algorithm?
Ans. The Sieve of Eratosthenes is an efficient algorithm for generating all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number as composite, leaving behind only the prime numbers. The process continues until all numbers have been processed. This algorithm significantly reduces the number of computations required compared to traditional methods.

Other Python Programs
Python program to reverse a number
Python program for heap sort
Python program to check armstrong number
Python program to check leap year
Python program to convert celsius to fahrenheit
Python program to find factorial of a number
Python program to reverse a linked list
Python Program to find the middle of a linked list using only one traversal
Python Program to Add Two Numbers
Python Program to Check Palindrome Number
Python Program to Print the Fibonacci Series
Python Loop Program
Anagram Program in Python
Fizzbuzz Program in Python
String Programs in Python
List Program in Python