patternjavascriptMinor
Project Euler #41 - pandigital prime
Viewed 0 times
pandigitalprojectprimeeuler
Problem
I've written a solution to Euler 41:
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?
But it feels like I could compress the code down instead of having 30 lines of for loops. To briefly explain how it works:
I generate all pandigital numbers through the generate function which features 9 nested for loops which continue if their value is equal to a higher loop or if they would make a number longer than what is required. The generated numbers are then prime checked. This is a bruteforce method.
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?
But it feels like I could compress the code down instead of having 30 lines of for loops. To briefly explain how it works:
I generate all pandigital numbers through the generate function which features 9 nested for loops which continue if their value is equal to a higher loop or if they would make a number longer than what is required. The generated numbers are then prime checked. This is a bruteforce method.
var time = new Date;
var buffer = [];
var greatest = 0;
function isPrime(number) {
var s = Math.sqrt(number);
for (var b = 2; b = 0; i--) {
if (isPrime(buffer[i])) {
greatest = buffer[i];
break;
}
}
var time1 = new Date;
console.log(greatest, 'took:', time1 - time, 'ms');Solution
I think this is a bit over engineered. Let's talk our way through the problem.
-
We need to test each number as a prime.
Here's a nice optimised
-
If it is prime we need to test each number is pandigital. We should only need to loop once. If we make a set of the digits in a number, then the length of the set will be equal to the total count of digits in the number.
-
Then you just need to write the loop:
-
Now it's your job to optimise these ideas so that this process doesn't take absolutely forever.
- By definition we know the highest pandigital number is 987654321.
- We need to loop through each odd number between 1 and 987654321.
-
We need to test each number as a prime.
Here's a nice optimised
isPrime function from here.function isPrime(number) {
var start = 2;
while (start 1;
}-
If it is prime we need to test each number is pandigital. We should only need to loop once. If we make a set of the digits in a number, then the length of the set will be equal to the total count of digits in the number.
function isPandigital(number) {
var numStr = number.toString(),
digits = [];
for (var digit in numStr) {
if (numStr.hasOwnProperty(digit) && digits.indexOf(digit) === -1)
digits.push(digit);
}
return digits.length === numStr.length;
}-
Then you just need to write the loop:
var pandigitalPrimes = [];
for (var n = 1; n <= 987654321; n+=2) {
if (isPrime(n) && isPandigital(n)) pandigitalPrimes.push(n);
}-
Now it's your job to optimise these ideas so that this process doesn't take absolutely forever.
Code Snippets
function isPrime(number) {
var start = 2;
while (start <= Math.sqrt(number)) {
if (number % start++ < 1) return false;
}
return number > 1;
}function isPandigital(number) {
var numStr = number.toString(),
digits = [];
for (var digit in numStr) {
if (numStr.hasOwnProperty(digit) && digits.indexOf(digit) === -1)
digits.push(digit);
}
return digits.length === numStr.length;
}var pandigitalPrimes = [];
for (var n = 1; n <= 987654321; n+=2) {
if (isPrime(n) && isPandigital(n)) pandigitalPrimes.push(n);
}Context
StackExchange Code Review Q#41037, answer score: 3
Revisions (0)
No revisions yet.