Prime Numbers: A Computational Perspective

Unless you understand the beauty of Prime numbers, you won’t run behind them. Well, I leave it as an exercise for the reader to find their beauty. To get a feel of how important Primes are, try writing a simple code to find if the given number is Prime [Wisely choose your algorithm!]. Now, put a massive Prime number (Yes, you can use the web to find these massive primes) having 20 digits and see what your code returns. If at all you perform this exercise [though imaginary], I assume that you have got some insight into what I’m trying to convince. So, the principle which we use in our welfare is that Prime numbers do not have any factors other than themselves! Thus, if you have a pair of 20-30 digit Primes then you may multiply them and use it to encrypt your data, and let the intruder take years to find your data. I won’t go into details of encryption, for it will make us deviate from the title. If you have used the Euclid’s algorithm (Which reduces the complexity from O (n) to O () for the primality search and if you have an inquisitive mind then you may ask: Are there any more such algorithms? I’m glad you asked! And I’m blushing here to explain them. You may refer, as I did, to the ‘so-called’...

Read More