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
Your algorithm using indexOf
findCircularPrimes1(100000);
pending…
My algoirthm using hash
findCircularPrimes2(100000);
pending…
200_success
solution_200_success(100000);
pending…

Compare results of other browsers

Revisions

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

0 Comments