HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMinor

Project Euler #41 - pandigital prime

Submitted by: @import:stackexchange-codereview··
0
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.

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.

  • 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.