Checking for circular primes - Project Euler Problem 35

Question

I have been trying to solve Project Euler problem number 35. The problem is to find:

How many circular primes are there below one million?

A circular prime is a prime where all the rotations of its digits are primes too. E.g. 197 is a circular prime as 197, 971, and 719 are all primes too.

Initially I was "brute-forcing" it by checking for divisors of the number up to its square root. However, I've realised how inefficient this was when the browser crashed above 10,000. Then I've tried using the Sieve of Eratosthenes, and now it can calculate the primes up to 1 million in ~4 seconds.

However, the part that is still to inefficient is the function to check if the primes are circular. I have made a few changes, but the browser still crashes above 100,000. What extra changes can I make?

//Erastosthenes sieve
function findPrimes(range) {
    var numbers = [1];
    var prime = 2;
    var primesArr = [2]

    //Stop searching once prime is as big as range
    while(prime < range) {
        //Fill var numbers all mulitipes of prime
        for(var i = 1; i <= range && prime * i <= range ; ++i) {
            numbers[prime * i - 1] = prime * i;
        }
        //Move onto the next prime
        while(numbers[prime-1] !== undefined) {
            ++prime;
        }
        //Add current prime to the array
        primesArr.push(prime);
    }
    //Delete the last prime which is bigger than range
    primesArr.pop();
    return primesArr;

}

//Find primes within range which are circular primes
function findCircularPrimes(range) {
    //Generate array of primes from findPrimes array
    var primes = findPrimes(range);
    var circularPrimes = [];
    //Loop through each of the primes
    for(var i = 0; i < primes.length; ++i) {
        //Split current prime into an array
        var numArr = primes[i].toString().split('');
        var truefalse = true;
        //Cycle through each of the digits and check if its a prime (and therefore a member of primes)
        for (var j = 0; j < numArr.length; ++j) {
            numArr.push(numArr.shift());
            //If current rotation is not a prime break the loop and 'return' false
            if (primes.indexOf(Number(numArr.join(''))) === -1) {
                truefalse = false;
                break;
            }
        }
        //If truefalse variable is true add circular prime to array
        if(truefalse) {
            circularPrimes.push(primes[i]);
        }

    }

    return circularPrimes;
}
var then = Date.now();
var primes = findCircularPrimes(100000).length
alert(primes);

Answer 1

Updated since reading the wikipedia definition of circular prime

There are a few things I would recommend you change in your findCircularPrimes algorithm. First, you should note the algorithm is O(d*n^2) where d is the length of the max digit. If we use a hash instead of an array to store all the primes we can stop using .indexOf() to check if a number is prime, making our algorithm O(d*n).

Another note is that javascript will represent large numbers in scientific notation. This is probably not important as your algorithm will crash the browser before it becomes an issue :)

I've re-implemented your algorithm using es5 methods reduce to create the primeHash and filter to produce the circularPrime list, but your old approach will work as well.

Edit stole @200_success much faster rotate function to make the comparison a bit fairer and updated the jsperf :)

var LN10 = Math.log(10);
// Rotates the least-significant base-10 digit to the front
function rotate(number) {
    return (number / 10 >> 0) +
           (number % 10) * Math.pow(10, Math.floor(Math.log(number) / LN10));
}
//Find primes within range which are circular primes
function findCircularPrimes(range) {

    var primes = findPrimes(range);

    //use a hash of primes for faster lookup
    var primeHash = primes.reduce(function(memo, prime) {
        memo[prime] = true;
        return memo;
    }, {});

    //use a hash of primes for faster lookup
    var circularPrimes = primes.filter(function(prime) {
        //check ciruclar primes
        var nextDigit = prime;
        while( (nextDigit = rotate(nextDigit)) !== prime) {
            if(! (nextDigit in primeHash)) {
                return false;
            }
        }

        return true;
    });

    return circularPrimes;
}

Performance test of your implementation vs mine (original set of tests)

Answer 2

Three performance killers, I believe, are:

• Rotating numbers via stringification

  Rotating the digits of a number using math operations turns out to be about 50⨉ faster than what you are doing.

• Failing to pre-allocate the Sieve of Eratosthenes array

  Whenever you build a large array, it's better to ask for the memory all at once than to ask for a little bit at a time.

• Taking results out of the Sieve of Eratosthenes array

  While a hash does give constant-time lookup, so does an array — and arrays are simpler. Since you've already built the array, it's fastest to use it as is.

Here is a solution, which is optimized more for performance than for clarity.

// Erastosthenes sieve; range is exclusive upper bound.
// Returns an array where element [n] is falsy if n is prime.
function sieve(range) {
    var nonPrime = [];
    nonPrime.length = range;  // Allocate the array all at once
    nonPrime[0] = nonPrime[1] = true;

    for (var i = 2; i < nonPrime.length; i++) {
        if (!nonPrime[i]) {
            for (var j = i * i; j < nonPrime.length; j += i) {
                nonPrime[j] = true;
            }
        }
    }
    return nonPrime;
}

var LN10 = Math.log(10);

// Rotates the least-significant base-10 digit to the front
function rotate(number) {
    return (number / 10 >> 0) +
           (number % 10) * Math.pow(10, Math.floor(Math.log(number) / LN10));
}

// Count circular primes less than an upper bound; the range must be a power of 10.
function countCircularPrimes(range) {
    // Array where element [n] is true if n is non-prime.
    // Later, we will also eliminate numbers that fail the digit circularity test.
    var eliminated = sieve(range);

    var circularPrimeCount = 0;
    for (var candidate = 0; candidate < eliminated.length; ++candidate) {
        if (!eliminated[candidate]) {
            var c = 1;
            for (var n = rotate(candidate); n != candidate; n = rotate(n)) {
                if (eliminated[n]) { c = 0; break; }
                c++;
                eliminated[n] = true;
            }
            // If c > 0, then a cycle was detected
            // if (c) console.log("" + c + " circular primes for " + candidate);
            circularPrimeCount += c;
        }    
    }
    return circularPrimeCount;
}

countCircularPrimes(1000000);