I'm trying to solve Problem 41of project Euler in Java, by counting the number from 99888888 to 80000000(which took very long time :( ), I got 98765431 as an answer, but I'm getting that answer not correct. Could anyone please tell me the reason of not getting the correct answer and how can I speed my program?
+4
A:
A pandigital number doesn't needs to contain all numbers from 1 to 9, but all from 1 to length.
So, you'll need to try all permutations from 1 to 9 starting with 1 digit and going up, filtering all prime numbers and, then, taking largest one.
Rubens Farias
2010-01-17 13:16:49
This feels like the way to go. There are only 362880 permutations of 9 elements, so this feels feasible to compute in reasonable time.
Buhb
2010-01-17 13:35:55
Not really: 362880+40320+5040+720+120+24+6+2=409112 permutations (remember to add permutations with 8, 7, 6 digits and so on), containing 538 primes inside it
Rubens Farias
2010-01-17 13:58:09
Fact: If the sum of the base 10 digits of an integer is 0 mod 3, that integer is divisible by 3.Thus, every 9 digit and 8 digit pandigital number is divisible by 3 and cannot be a prime.
GregS
2010-01-17 15:07:48
Amazing fact, @GregS, ty =)
Rubens Farias
2010-01-17 19:25:12