finding if a number is prime LARGE NUMBERS

[9G6fSL3A]

I have a very large number in word ~6million digits long

I wish to make a program to check if it is prime.
Could anyone give me an idea of where to start?

[Tertius Kgatla]

Share your code and we will aid.

long long int number = ...

believe that should be long enough to hold

[Stewbond]

6 million digits won't fit into a long long int. He's probably using some big number class.

regardless, he can still use the same approach regardless of how many digits there are:

template <class T>
bool isPrime(T number)
{
    for(T i(2); i < sqrt(number); ++i)
        if (number % i == 0)
            return false;
    return true;
}

Another method could be to create a table of primes and just check each of those.

Here I'm assuming that your big number class supports operators <, ==, %, and has a sqrt() overload.

[kbw]

You don't want to use a linear search for large primes, you have to do better.

Remember, finding primes is like finding random numbers in an exponentially growing range.

You can consider the Sieve of Eratosthenes, it's suitable for up to 10 million.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Mats]

A six million digit long number?! The only way is going to be to use a sieve and it's going to take a very very very long time. I would check it's not obviously divisible by any number using the last few digits and divisibility rules and if it passes that, then give up. :p

[JLBorges]

http://en.wikipedia.org/wiki/AKS_primality_test
Caveat: deterministic, but quite slow (8 hours or so for a 150 decimal digit number).

For a 6 million decimal digit number, you would want to use a probabilistic prime number test. http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test