# Circular primes

## JavaScript performance comparison

Revision 2 of this test case created by 200_success

## Preparation code

``````

<script>
Benchmark.prototype.setup = function() {
//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 findCircularPrimes1(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;
}

//Find primes within range which are circular primes

function findCircularPrimes2(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;
}, {});

var circularPrimes = primes.filter(function(prime) {
//check ciruclar primes
var digits = String(prime).split("");

//check each permutation of digits
for (var j = 0; j < digits.length; ++j) {
digits.push(digits.shift());
//If current rotation is not a prime break the loop and 'return' false
if (!(digits.join("") in primeHash)) {
return false;
}
}
return true;
});

return circularPrimes;
}

solution_200_success = (function() {

// 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;
}

return countCircularPrimes;

})();
};

</script>
``````

## Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
``findCircularPrimes1(100000);``
pending…
My algoirthm using hash
``findCircularPrimes2(100000);``
pending…
200_success
``solution_200_success(100000);``
pending…

## Revisions

You can edit these tests or add even more tests to this page by appending `/edit` to the URL.