Prime Number and their importance.
Hello everyone,
First, what is Prime number?
A number that is divisible only by 1 and itself is called a prime number.
Example: 5, 7, 11
But wait, what’s the use of it? Well, even I’ve invented a number called the Raj Number, which follows the rule that it must be divisible by both 3 and 4.
Example: 12, 24… 😆
Jokes apart, prime numbers actually have real-world applications. That’s why they are important.
After searching for an hour, I found an interesting example on the web. Let’s dive into it! 🚀
Every natural numbers can be factors of prime…Take any and try it
Ex: 24 => 6 X 4 =>3 X 2 X 2 X 2
This is one of the amazing facts I discovered during my search!
Now Take two prime p and q.
Ex: p=3 q=5
p x q = 15
Now if i give 15, ask to find out their prime factor..
You can easily find out..
Now myself hiding p and q, I give only p x q= 7.66331447 X 10¹⁴.. Try it to find out p and q.(I will tell answer for this in last part)
It may take you an hour or even a day, but for a machine, it’s a much smaller task and can be solved easily. 🚀
If a number is not prime, you can easily find its factors.
However, prime factors of extremely large numbers cannot be found in just a few seconds or minutes. This complexity is leveraged in network security.
In the real world, even larger numbers are used for encryption. For a deeper explanation, refer to this article.
Now time for problem
How to find if the number is prime or not ?
Consider the given number as N.
Steps are
- Check if the N is even number and N is not equal to 2, if it is then N is not prime. Exit
- Check if the N is equal to 2, If it is then N is prime. Exit
- If the above two conditions fails, then
I) From i=3,5,7,9………..until sqrt(n), check if n is divisible by any i.
II) If it is then N is not prime.Exit
III) If it is not then N is prime.Exit
Note: why sqrt(n). If n is having factors, then it smallest factor is present before or equal to sqrt(n)
Eg : Take the number as 75. Sqrt of 75 is 8.66. Then smallest factor of 75 is 3.
Eg: Take the another number which is prime 61. sqrt of 61 is 7.81. It is not having factors upto 7. So declare it as prime. Instead of going upto 61, we can tell like it is prime in 7th table.
And that two number is 98333371 and 77931713.
