prime-number

is a recursive function to check if a number is prime (and a benchmark to test how slow it is :)

KLP js-standard-style

Table of Contents

Is it 1 a prime? Some years ago I composed a djembe rhythm based on prime numbers, and it sounds better if 1 is considered prime. Casually, the algorithm implemented here defines 1 as a not prime.

Usage

As you might expect, you can do

const isPrime = require('prime-number')

console.log(isPrime(19)) // true

There is a list of few primes available, if you want to use it

const primeNumberList = require('prime-number/list')
console.log(primeNumberList)

You can benchmark other primality check algorithms.

const isPrime = require('yet-another-primality-check')
const benchmark = require('prime-number/benchmark')
const from = 1000
const to = Number.MAX_SAFE_INTEGER

benchmark(isPrime)(from, to)

Using a oneliner, let’s check few primality check packages found on npm.

# node -e "require('prime-number/benchmark')(require('prime-number'))(10000, 100000)"
Found 8363 primes
Primality benchmark: 44.703s

# node -e "require('prime-number/benchmark')(require('is-prime'))(10000, 100000)"
Found 8363 primes
Primality benchmark: 14.885ms

# node -e "require('prime-number/benchmark')(require('check-prime'))(10000, 100000)"
Found 8363 primes
primality benchmark: 61.613ms

So I can state that

My algorithm sucks! 🐸

Installation

With npm do

npm install prime-number

Or copy and paste the code below.

Source

First of all, do not check if num is an integer or positive or less than Number.MAX_SAFE_INTEGER. You can do it with some other function before calling primeNumber.

// Remember if a number is prime.
const memoize = { isPrime: {}, isNotPrime: {} }
memoize.isNotPrime[1] = true
memoize.isPrime[2] = true

/**
 * Check if a number is prime.
 *
 * @param {Number}
 *
 * @returns {Boolean}
 */

function primeNumber (num) {
  // Avoid computing twice.
  if (memoize.isPrime[num]) return true
  if (memoize.isNotPrime[num]) return false

  const knowPrimes = Object.keys(memoize.isPrime)

  for (let i = 0; i < knowPrimes.length; i++) {
    const p = Number(knowPrimes[i])

    if (num === p) return true

    if (num % p === 0) {
      memoize.isNotPrime[num] = true
      return false
    }
  }

  for (
    let i = 3;
    // Do not excede the square root of num.
    i * i <= num;
    // All prime numbers are 1 or 5 modulo 6.
    // Since we start with 3, this will do: 3 -> 5 -> 7 -> 11 ... +2 -> +4 -> +2 -> +4 ...
    i = i % 6 === 1 ? i + 4 : i + 2
  ) {
    if (primeNumber(i)) { // <-- Recursion here!
      if (num % i === 0) {
        memoize.isNotPrime[num] = true
        return false
      }
    }
  }

  memoize.isPrime[num] = true
  return true
}

Export primeNumber function

module.exports = primeNumber

License

MIT