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?



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");
                    Console.WriteLine(IsPrime(number) ? "Prime" : "Not prime");

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

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s