Sep 15, 2013 at 6:40am UTC
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?
Sep 15, 2013 at 6:55am UTC
Share your code and we will aid.
long long int number = ...
believe that should be long enough to hold
Sep 15, 2013 at 7:34am UTC
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:
1 2 3 4 5 6 7 8
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.
Last edited on Sep 15, 2013 at 7:40am UTC
Sep 15, 2013 at 11:38am UTC
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
Sep 15, 2013 at 12:37pm UTC
Last edited on Sep 15, 2013 at 1:00pm UTC