You may have recently read that the largest prime number having 22,338,618 digits was recently found. Which brings a question to mind that what the advantage of finding these prime numbers is. Prime numbers are natural numbers greater than one which are only divisible by one and themselves. All other natural numbers are known as composite numbers. Computers have long been used to determine higher prime numbers which can’t be otherwise checked by humans. In computers these are used in public key encryption algorithms like RSA. They are also used in hash tables and also for generating pseudo random numbers. Finding large prime numbers is a very difficult task and super computers running very fast and efficient programs are used for it.
Many efficient algorithms exist to determine whether a number is prime or not. For smaller numbers we can just apply trial division for successive odd numbers. However, this method is not very efficient and sieves are used which are comparatively faster. Some of the prime sieves are sieve of Eratosthenes, sieve of Sundaram etc.
Sieve of Eratosthenes is a prime number sieve. It is a simple, ancient algorithm used to find prime numbers up to a certain limit. It is one of the most efficient method to find all the small prime numbers and is faster than trial division. To find prime number first create a list of numbers from 2 to n. First select 2, the smallest prime number then remove all its multiples as possible prime numbers. Then select the next possible number and assign it as a prime number and remove all its multiples as a possible prime number and keep on doing this until all prime numbers in the list are found. A standard code of Sieve of Eratosthenes can find all primes up to N in time O(N log log N).
The Wonderful World of Algorithms 