Check whether a very big number is prime or not in C#

Problem source – HackeRrank – Running Time and Complexity

We all know how to check whether a number is prime number or not. As per the definition, a Prime number is a number that can be divisible only with 1 and itself. All other numbers are Non-Primes.

So, 1, 2, 5, 7, 11, 13, 19, 23, 29, 31 … are prime numbers, because all of these numbers can only be divided by either 1 or itself.

That’s theory, no lets see how actually we can check. Suppose you have a number n, so as per theory, if we can find any number other than 1 and n, that is perfect divisor then n is not a Prime number, otherwise it is.

If we try to implement above logic then we’ll have to try all the numbers from 2 to n, but wait a second and think one more time, the biggest divisor of a number can be half of the number.

so, in our case we don’t need to check all the numbers, just check till n/2. Because any number greater than n/2 can never be a divisor of n.

Awesome, now we just cut down half of the iterations and it’s really great in case of a very big number, like 1000000007.

But, half of 1000000007 is still a very big number. If you iterate it one at a time you might get timeout exception. So what do we do now?

hmmm….

hmmm…..

We can do one thing and it’ll solve our problem in case of very BIG NUMBERS. Instead of n/e, if you loop till Square root of n, then we are good. The logic behind this is:

If a number n is not a prime, it can be factored into two factors a and b:

n = a*b

If both a and b were greater than the square root of n, a*b would be greater than n. So at least one of those factors must be less than or equal to the square root of n, and to check if n is prime, we only need to test for factors less than or equal to the square root.

 

So now, we have solution of all the problems, no lets see the actual code:

    class BigPrimeNumbersIssue
    {
        static void Main(string[] args)
        {
            int T = Convert.ToInt16(Console.ReadLine());
            for (int i = 0; i < T; i++)
            {
                decimal number = Convert.ToDecimal(Console.ReadLine());
                if (number == 1)
                {
                    Console.WriteLine("Not prime");
                    continue;
                }
                else
                {
                    Console.WriteLine(IsPrime(number) ? "Prime" : "Not prime");
                }
            }
            Console.ReadKey();
        }

        private static bool IsPrime( decimal number)
        {
            bool isPrime = true;
            for (int j = 2; j * j <= number; j++)
            {
                if (number % j == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            return isPrime;
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s