Prime numbers are fascinating mathematical entities that have intrigued mathematicians for centuries. A prime number is a natural number greater than 1 that is divisible only by 1 and itself, with no other factors. These numbers possess a unique quality, making them indispensable in various fields such as cryptography, computer science, and number theory. They have a mystique that arises from their unpredictability and apparent randomness, yet they follow precise patterns and exhibit extraordinary properties. In this blog, we will explore prime numbers and delve into the implementation of a prime number program in Python. By the end, you will have a solid understanding of prime numbers and the ability to identify them using the power of programming. Let’s embark on this mathematical journey and unlock the secrets of prime numbers with Python!
What is a prime number?
Prime numbers are a subset of natural numbers whose factors are only 1 and the number itself. Why are we worried about prime numbers and obtaining prime numbers? Where can they be possibly used? We shall understand the entire concept of prime numbers in this article. Let’s get started.
The factors for a given number are those numbers that result in a zero remainder on division. These are of prime significance in the area of cryptography to enable public and private keys. Essentially, the internet is stable today because of cryptography, and this branch relies heavily on prime numbers.
Is 1 a prime number?
Let us take a step back and pay close attention to the definition of prime numbers. They are defined as ‘the natural numbers greater than 1 that cannot be formed by multiplying two smaller natural numbers’. A natural number that is greater than 1 but is not a prime number is known as a composite number.
Therefore, we cannot include 1 in the list of prime numbers. All lists of prime numbers begin with 2. Thus, the smallest prime number is 2 and not 1.
Co-prime numbers
Let us learn further. What if we have two prime numbers? What is the relationship between any two prime numbers? The greatest common divisor between two prime numbers is 1. Therefore, any pair of prime numbers results in co-primes. Co-prime numbers are the pair of numbers whose greatest common factor is 1. We can also have non-prime number pairs and prime and non-prime number pairs. For example, consider the number of pairs-
- (25, 36)
- (48, 65)
- (6,25)
- (3,2)
Check if a given String is a Palindrome in Python
Smallest and largest prime number
Now that we have considered primes, what is the range of the prime numbers? We already know that the smallest prime number is 2.
What could be the largest prime number?
Well, this has some interesting trivia related to it. In the year 2018, Patrick Laroche of the Great Internet Mersenne Prime Search found the largest prime number, 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. That’s a huge number.
For now, let us focus on implementing various problems related to prime numbers. These problem statements are as follows:
- Recognizing whether they are prime or not
- Obtaining the set of prime numbers between a range of numbers
- Recognizing whether they are prime or not.
This can be done in two ways. Let us consider the first method. Checking for all the numbers between 2 and the number itself for factors. Let us implement the same. Always start with the following algorithm-
Algorithm
- Initialize a for loop starting from 2 and ending at the number
- Check if the number is divisible by 2
- Repeat till the number -1 is checked for
- In case, the number is divisible by any of the numbers, the number is not prime
- Else, it is a prime number
num = int(input("Enter the number: "))
if num > 1:
# check for factors
for i in range(2,num):
if (num % i) == 0:
print(num,"is not a prime number")
print(i,"times",num//i,"is",num)
break
else:
print(num,"is a prime number")
# if input number is less than
# or equal to 1, it is not prime
else:
print(num,"is not a prime number")
Let us consider the efficient solution, wherein we can reduce the computation into half. We check for factors only until the square root of the number. Consider 36: its factors are 1,2,3,4,6,9,12,18 and 36.
Square root of 36 is 6. Until 6, there are 4 factors apart from 1. Hence, it’s not prime.
Consider 73. Its square root is 8.5. We round it off to 9. There are no factors apart from 1 for 73 till 9. Hence it is a prime number.
Now before we get into the details of Python Program for prime number, maybe get a free refresher course on the Fundamentals of Python. This course covers all the basic and advanced concepts of Python programming like Python Data Structures, Variables, Operators, Flow Control Statements, and OOPs. It even offers a certificate on completion which could definitely boost your resume.
Python Program for prime number
Let us implement the logic in python–
Algorithm:
- Initialize a for loop starting from 2 ending at the integer value of the floor of the square root of the number
- Check if the number is divisible by 2
- Repeat till the square root of the number is checked for.
- In case, the number is divisible by any of the numbers, the number is not prime
- Else, it is a prime number
import math
def primeCheck(x):
sta = 1
for i in range(2,int(math.sqrt(x))+1): # range[2,sqrt(num)]
if(x%i==0):
sta=0
print("Not Prime")
break
else:
continue
if(sta==1):
print("Prime")
return sta
num = int(input("Enter the number: "))
ret = primeCheck(num)
We define a function primeCheck which takes in input as the number to be checked for and returns the status. Variable sta is a variable that takes 0 or 1.
Let us consider the problem of recognizing prime numbers in a given range:
Algorithm:
- Initialize a for loop between the lower and upper ranges
- Use the primeCheck function to check if the number is a prime or not
- If not prime, break the loop to the next outer loop
- If prime, print it.
- Run the for loop till the upperRange is reached.
l_range = int(input("Enter Lower Range: "))
u_range = int(input("Enter Upper Range: "))
print("Prime numbers between", l_range, "and", u_range, "are:")
for num in range(l_range, u_range + 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)
In this tutorial, we have covered every topic related to prime numbers. We hope you enjoyed reading the article. For more articles on machine learning and python, stay tuned!
Learn how to print the Fibonacci Series in Python.
Embarking on a journey towards a career in data science opens up a world of limitless possibilities. Whether you’re an aspiring data scientist or someone intrigued by the power of data, understanding the key factors that contribute to success in this field is crucial. The below path will guide you to become a proficient data scientist.
