prime_rotations.js

/*
 A number is called a circular prime if it is prime and all of its rotations are primes.

 For example the number 197 has two rotations: 971, and 719.
 Both of them are prime.
 There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.


 How many circular primes are there below N?


 1 <= N <= 1000000



 Test Cases


 There are 0 circular primes below 1.

 There are 4 circular primes below 10.

 There are 13 circular primes below 100.

 There are 25 circular primes below 1000.

 There are 33 circular primes below 10000.
 * */

"use strict";
var assert = require('assert');

// cache of prime numbers
var primes = [];
function cacheIsPrime(x, p){
    primes[x] = p;
}
function getCachedPrime(x){
    return primes[x];
}

function isPrime(x) {
    var cached = getCachedPrime(x)
    if (cached !== undefined) {
        return cached;
    }
    for (var i = 2; i <= x / 2; i++) {
        //console.log(x, i, x%i);

        if (x % i === 0) {
            cacheIsPrime(x, false);
            return false;
        }
    }
    cacheIsPrime(x, true);
    return true;

}

function nextPrime(x) {
    x++;
    while (!isPrime(x)){
        x++;
    }
    return x;
};

function getRotations(x){
    var result = [];
    x = x.toString().split('');
    //console.log(x);
    for(var i=0; i< x.length-1; i++){
        // rotate
        x.unshift(x.pop());
        result.push(x.join(''));
    }
    return result;
}

//console.log('Rotations of 197', getRotations(197));

function isCircularPrime(x) {
    var r = getRotations(x);
    //console.log('Rotations of %s', x, r);
    for(var i=0; i< r.length; i++){
        if (!isPrime(r[i])){
            return false;
        }
    }
    return true;
}

function solution(n) {
    if (n < 2) return 0;

    var result = 0;
    var prime = 2;

    while(prime < n){
//        console.log('checking if %s is circular prime', prime);
        if (isCircularPrime(prime)){
            console.log('found circular prime', prime);
            result++;
        }
        prime = nextPrime(prime);
    }

    return result;
}



assert(isPrime(3), '3 is prime');
assert(isPrime(2));
assert(!isPrime(4));
assert(isPrime(5));
assert(isPrime(7));
assert(!isPrime(8));

assert.equal(nextPrime(2), 3);
assert.equal(nextPrime(3), 5);
assert.equal(nextPrime(5), 7);
assert.equal(nextPrime(7), 11);

assert(isCircularPrime(197));

assert.equal(solution(1), 0, 'There are 0 circular primes below 1');
assert.equal(solution(10), 4, 'There are 4 circular primes below 10');
assert.equal(solution(100), 13, 'There are 13 circular primes below 100');
assert.equal(solution(1000), 25, 'There are 25 circular primes below 1000');
assert.equal(solution(10000), 33, 'There are 33 circular primes below 10000');