Circular primes

JavaScript performance comparison

Revision 3 of this test case created by Emanuel Jackstare

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;
  
  }
  
  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 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
              //alg based on https://gist.github.com/jpillora/4435759
              var nextDigit = prime;
              while( (nextDigit = rotate(nextDigit)) !== prime) {
                  if(! (nextDigit 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;
  }
  
  
  // 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…
Megawac algoirthm
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