Can you help me in understanding the approach of this problem
I have seen couple of solutions(link text), but both of them trying to pre-populate initial 170 prime numbers. I don’t understand why.
I was thinking of basic idea.
a) First I shall calculate all primes which is less than the square root of the given number
b) Will try to divide that given number by all this primes.
Not sure how do I calculate the (a) part since number is huge. Any help would be great.
@soumyaukil >> Read about Sieve of Eratosthenes, Sieve of Atkin, AKS primality test, Miller-Rabin primality test to name a few.
UPDATE
How about this solution?
Which algorithm does it use
It uses both Miller-Rabin & Lucas-Lehmer test.
Oracle says this:
public boolean isProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it’s definitely composite. If certainty is ≤ 0, true is returned.
Parameters:
certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter.
Returns:
true if this BigInteger is probably prime, false if it’s definitely composite.