Checking for circular primes - Project Euler Problem 35

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)
fo

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(dn^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(dn).

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)

StackExchange Code Review Q#38718, answer score: 6