We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.
What is the largest n-digit pandigital prime that exists?
analyse:
The 8 and 9 digit pandigital 987654321 are divideble by 3 (Sum digits divide evenly by 3).
and thus are composit numbers and no primes.
So we start with a 7 digit padigital number 7654321.
Performance improvements:
1) Use permutation to generate pandigitals. This reduces loop from 6419754 to 5040.
2) Use the fast Miller-Rabin test to check if a big number is a prime.
Problem41 = 7652413 elapsed time: 2 ms. Test Passed.
Geen opmerkingen:
Een reactie posten