John Sadusky wrote:
Alternative Solution: From my research i found out that finding prime factors of A & B will reduce the execution time considerably (< 3 sec), but i'm not sure how to apply it.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:Also: why are you using BigInteger? You construct these from integers and I can't think of any reason
why that would be beneficial.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:For the prime number method, for down to earth ProjectEuler problems, I usually start with generating a HashMap and an
ArrayList of primes. Using the sieve of Erathotenes is a very fast method to do that.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
fred rosenberger wrote:knowing the prime factors of A and B should help you reduce the number of pairs of (a,b) you have to check. If A and B both have 7 as a factor, you can eliminate all a and b that are multiples of 7.
Winston Gutkowski wrote:
For relatively small numbers, sure; but isProbablePrime() is also pretty darn fast for small p (probability) values. With p = 4, for example, if the number you supply is not prime, the method will return false on average 15 times out of 16, and it will execute very quickly. If it returns true, then you can try a deterministic solution (usually slower) to make sure that it really is prime.
And the time it takes is roughly proportional to the p value, so p=6 will take about 50% longer than p=4, but you reduce the chances of a "false true" to 1 in 64.
Winston
There are three kinds of actuaries: those who can count, and those who can't.