I am having trouble trying to check if a number (greater than 10^50) is prime or not...
the general algorathm for checking it by taking modulus is very ineffective as you might see..
Please suggest any other algorithm options...
*{originally I was trying this question..
and the last terms turn out to be greater than 10^50...
{Given the first few Fibonacci numbers below:
1 1 2 3 5 8 13 21 ...
How many of the first 250 Fibonacci numbers are prime? Note that you are seeing the first 8 above.
}
}
You need a bignum class to hold your number to begin with. How else are you going to store an integer capable of holding a 51 digit integral value? http://en.wikipedia.org/wiki/Bignum#Libraries
#include <iostream>
#include <limits>
int main()
{
std::cout << "The number of digits a double can accurately hold is: " ;
std::cout << std::numeric_limits<double>::digits10 << '\n' ;
}
Robert Sedgewick has a chapter on algorithms to calculate with large numbers. It is based on arrays of coefficients representing the large number as polynom.
A quick search on Google didn't found the algorithm, but maybe you are more successful.
EDIT: At least I found this: http://www.algorithmist.com/index.php/BigNum