JavaScript: Check if number is prime with recursion

Question

I am bit confused on how to solve this problem. I need all the prime numbers to return true. If not return false--I see that my logic is including 2 and that returns 0 so it automatically returns false, because 2 has a remainder of 0.

  

  function isPrime(num, div = 2) {
      // BASE CASE: 
     
      if(num <= div ) return false; // IF num less than OR equal to  2 RETURN false 
      
      // IF num MOD has a remainder of zero   
         
      if(num % 2 === 0) return false  // RETURN false 
      
      return true; // RETURN true
     
      // RECURSIVE CALL:

      return isPrime(num)
    }

    console.log(isPrime(1)); //-> false
    console.log(isPrime(2)); //-> true
    console.log(isPrime(3)); //-> true
    console.log(isPrime(4)); //-> false

Answer 1

There is no need for recursion. Just test all odd integers from 3 to the square root of the number as possible factors for the best performance.

function isPrime(num){
      if(num === 2) return true;
      if(num < 2 || num % 2 === 0) return false;
      for(let i = 3; i * i <= num; i += 2)
          if(num % i === 0) return false;
      return true;
}

If you really need to use recursion, the above idea can be implemented by accepting a factor as the second argument and incrementing it by 2 when recursing.

function isPrime(num, div = 3){
      if(num === 2) return true;
      if(num < 2 || num % 2 === 0)  return false;
      if(div * div > num) return true;
      if(num % div === 0) return false;
      return isPrime(num, div + 2);
}

Answer 2

Recursion is fun! Let's see how we can compute prime numbers by imagining an emptyStream, the ability to create a new stream and the ability to filter a stream -

import { stream, emptyStream, filter } from "./Stream"

const numbers = (n = 0) =>
  stream(n, _ => numbers(n + 1))

const sieve = (t = numbers(2)) =>
  t === emptyStream
    ? t
    : stream
        ( t.value
        , _ =>
            sieve
              ( filter
                  ( t.next
                  , v => v % t.value !== 0
                  )
              )
        )

This technique is known as the Sieve of Eratosthenes. Using additional stream functions we will take the first 1,000 items and convert the result toArray -

import { take, toArray } from "./Stream"

const result = 
  toArray(take(sieve(), 1000))
  
console.log(JSON.stringify(result))
// [2,3,5,7,11,13,17,19,23, ... ,7901,7907,7919]

You can implement Stream however you like. Here's one possible implementation -

// Stream.js

const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) =>
  ( { value
    , get next ()
      { delete this.next
      ; return this.next = next()
      }
    }
  )

const filter = (t = emptyStream, f = identity) =>
  t === emptyStream
    ? t
: Boolean(f(t.value))
    ? stream
        ( t.value
        , _ => filter(t.next, f)
        )
: filter(t.next, f)

const take = (t = emptyStream, n = 0) =>
  t === emptyStream || n <= 0
    ? emptyStream
    : stream(t.value, _ => take(t.next, n - 1))
    
const toArray = (t = emptyStream) =>
  t === emptyStream
    ? []
    : [ t.value, ...toArray(t.next) ]

export { emptyStream, stream, filter, take, toArray }

---

Expand the snippet below to compute the first 1,000 primes in your browser -

// Stream.js
const emptyStream =
  Symbol('emptyStream')

const stream = (value, next) =>
  ( { value
    , get next ()
      { delete this.next
      ; return this.next = next()
      }
    }
  )
  
const filter = (t = emptyStream, f = identity) =>
  t === emptyStream
    ? t
: Boolean(f(t.value))
    ? stream
        ( t.value
        , _ => filter(t.next, f)
        )
: filter(t.next, f)

const take = (t = emptyStream, n = 0) =>
  t === emptyStream || n <= 0
    ? emptyStream
    : stream(t.value, _ => take(t.next, n - 1))
    
const toArray = (t = emptyStream) =>
  t === emptyStream
    ? []
    : [ t.value, ...toArray(t.next) ]

// Main.js
const numbers = (n = 0) =>
  stream(n, _ => numbers(n + 1))

const sieve = (t = numbers(2)) =>
  t === emptyStream
    ? t
    : stream
        ( t.value
        , _ =>
            sieve
              ( filter
                  ( t.next
                  , v => v % t.value !== 0
                  )
              )
        )

const result = 
  toArray(take(sieve(), 1000))
  
document.body.textContent = result.join(", ")

Output

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919

---

Did that last program overflow your stack? No problem, because we used a module, our streams are separated by a barrier of abstraction. This allows us to make changes to Stream without affecting our Main module. The offenders can be modified to use a while loop if larger computations are necessary -

// Stream.js

const emptyStream = //...

const stream = //...

const take = // ...

function filter (t = emptyStream, f = identity)
{ while (t !== emptyStream)
    if (Boolean(f(t.value)))
      return stream
        ( t.value
        , _ => filter(t.next, f)
        )
    else
      t = t.next      // <-- advance stream t without recursion
  return t
}

function toArray (t = emptyStream)
{ let r = []
  while (t !== emptyStream)
    ( r.push(t.value)
    , t = t.next      // <-- advance stream t without recursion
    )
  return r
}

Answer 3

I came for the recursion, but Thankyou already has an excellent answer for how to deal with this recursively using some useful abstractions.

That answer used a version of the Sieve of Eratosthenes. I'd just like to point out another version of that sieve, one less elegant but I believe quite a bit more performant.

The basic implementation is this generator function:

const sieve = function * () {
    const C = {} // known composite numbers
    let q = 2
    while (q < Infinity) {
        if (C [q]) {
            C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n]  )
            delete C [q]
        } else {
            C [2 * q] = [q]
            yield q
        }
        q += 1
    }
}

The Sieve wants us to cross off all the multiples of a given prime. This is fine if we start with a fixed list of numbers, but here we want to deal with streams of values, with no fixed upper bound. Instead, at any multiple of a prime, we cross off only the next multiple that we would hit. We track this with the local variable C, which holds a bit of information about prime multiples.

Let's say we've reached a test value of 11. Then we've already seen the primes of 2, 3, 5, and 7. The next multiple of 2 is 12; the next multiple of 3 is also 12, the next multiple of 5 is 15 and the next multiple of 7 is 14. At this point C will look like this:

{
  12: [3, 2],
  14: [7],
  15: [5]
}

Because 11 is not in this list, we add 2 * 11 to C, and yield it back as our next prime. So when we check 12, C will look like this:

{
  12: [3, 2],
  14: [7],
  15: [5],
  22: [11]
}

But now 12 is on this object, so 12 is not prime. And we have to do some more adjusting. We're going to remove 12 from that list, but we have to place our 2 and 3 values on their next multiples. The next multiple of 2 after 12 is 14, so we'll update the value at 14 to include 2. The next value multiple of 3 after 12 is 15, so we'll update the value at 15 to include 3.

And now, when we hit 13, C holds

{
  14: [7, 2],
  15: [5, 3],
  22: [11]
}

And because 13 is not in C we know that it's prime. We will will yield it and add 26 (2 * 13) to C with the value 13. And this will lead us to a continuing stream of prime numbers. The state we will maintain is simply the collection of next multiples of each prime found so far.

A sharp eye might have noticed some extra work going on here. When adding the first multiple of, say, 7 to our list, we don't really need to start at 14; that will already be crossed off as a multiple of 2. And 21 is a multiple of 3, 28 a multiple of 4 (and hence of 2), 35 a multiple of 5, and 42 a multiple of 6 (and hence of 2 and 3.) The first multiple we need to check specifically is 49. And in general, when we add a prime, p, the first multiple we will need to check is p ** 2. We can fix that by replacing this:

            C [2 * q] = [q]

with this:

            C [q * q] = [q]

We can test this function like this:

const iterator = sieve()

console.log(iterator.next()) //=> {value: 2, done: false}
console.log(iterator.next()) //=> {value: 3, done: false}
console.log(iterator.next()) //=> {value: 5, done: false}
console.log(iterator.next()) //=> {value: 7, done: false}
console.log(iterator.next()) //=> {value: 11, done: false}
console.log(iterator.next()) //=> {value: 13, done: false}

And we could write a take function as seen in Thankyou's answer. And that's probably the best way to handle this. But we can also alter this function to end either after n results ("find the first n primes") or when the value exceeds n ("find all the primes up to n".)

The latter is trivial: just add the parameter max and replace our use of Infinity with it. The former is only slightly more difficult. Here's one version:

const sieve = function * (count) {
    const C = {} // known composite numbers
    let n = 0
    let q = 2
    while (n < count) {
         if (C [q]) {
            C [q] .forEach (n => C [n + q] = [... (C [n + q] || []), n]  )
            delete C [q]
        } else {
            C [q * q] = [q]
            n += 1
            yield q
        }
        q += 1
    }
};

console .log ([... sieve(1000)])

.as-console-wrapper {max-height: 100% !important; top: 0}

Logically, our composites internal data structure would not be an Object mapping integers to arrays of integers. Clearly the most appropriate structure would be a Map mapping integers to Sets of integers. We can certainly write it that way:

const sieve = function * (count) {
    const C = new Map () // known composite numbers
    let n = 0
    let q = 2
    while (n < count) {
        if (C .has (q)) {
            [... C .get (q)] .forEach (
              n => C .set (n + q, (C .get (n + q) || new Set ()) .add (n))
            )
            C .delete (q)
        } else {
            C .set (q * q, new Set ([q]))
            n += 1;
            yield q
        }
        q += 1
    }
};

For one reason or another I find this less readable than its Object-Array counterpart. I haven't tested performance, but I would be surprised if this is significantly faster (or slower.) But it works the same way.

Noe of this is written in my usual style. While we could probably achieve something that avoids mutating an internal structure by using recursion, no technique leaps to mind.

---

More information about this version of the Sieve and its relative complexity is in the wonderful The Genuine Sieve of Eratosthenes, by Melissa E. O’Neill. The paper is academic, but still quite readable. And if you can read Haskell it should be easy to take in.