Checking if a number is prime - A faster way

In order to check if a number(say n) is prime or not, you take the following steps:

1. If n is even and n!=2, it is not a prime.
2. Check for the square root of n, say x. 
3. If x is not divisible by any prime number less than x, it is a prime.
4. Again while checking for all prime numbers less than x, you only need to look for the odd numbers. 

Example, 

1. n=9923. We check if 9923 is prime or not.
2. Since 9923 is odd, 2 is discarded.
3. Square root of 9923 is roughly 99.614, we round it off to 100.
4. Now we check if any prime less than 100 divides 9923.
5. Since we have to check for primes, for convenience, we opt for a larger subset, all odd numbers.
6. Set A={3,5,7,9,11,...,91,93,95,97,99}.
7. We check if any of these numbers divides n.
8. More efficiency is possible if we apply Sieve of Eratosthenes and strike out the numbers divisible by 3,5, and 7. We only will need to check the divisibility from the remaining numbers.

Since, we didn't check for all the numbers from 1 to 100 and only the odd ones, it made the program 200% efficient. Forget checking all numbers from 1 to 9922.

© Rishabh Bidya