Really large prime numbers

[saurabhkoolkumar]

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.
}
}

[kbw]

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

[saurabhkoolkumar]

I think double can easily store that big value..

[cire]

#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' ;
}

[D4S8vCM9]

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

[saurabhkoolkumar]

thanx guys..
that was really helpful..