Project Euler 7: 10001 Prime in Functional Programming (FP)

Question

I wanted to practice functional programming (fp) without using any library but using vanilla JS only. So I took a problem from Project Euler:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

This is my solution:

(function () {
  'use strict';

  function* checkForPrime(n) {
    let m = Math.floor(Math.sqrt(n) + 1);
    while (true) {
      if (n < 2) {
        yield false;
        return;
      }
      if (m < 2 || n === 2 || n === 3) {
        yield true;
        return;
      }
      if (n % m === 0) {
        yield false;
        return;
      }
      m--;
    }
  }

  const isPrime = n => checkForPrime(n)
    .next();

  function* searchForPrimeNumbers(max) {
    let primeCounter = 0;
    let newPrimeNumber = 1;
    let runningNumber = 1;
    while (true) {
      if (primeCounter === max) {
        yield newPrimeNumber;
        return newPrimeNumber;
      }
      if (isPrime(runningNumber)
        .value) {
        newPrimeNumber = runningNumber;
        primeCounter = primeCounter + 1;
      }
      runningNumber++;
    }
  }

  const finalsolution = searchForPrimeNumbers(1e4 + 1);

  const findPrimeTill10001 = () => {
    return finalsolution.next()
      .value ? finalsolution.next()
      .value : findPrimeTill10001();
  };

  const solution = findPrimeTill10001();
  console.log(solution);
})();

As you can see, it is not consistent with the idea of FP. First I wanted to write it using recursion but I hit the stack limit. Therefore I used generators (and loops). That was the only solution I could come up with that resembles FP.

Any suggestions how to write in FP without any additional FP-Library (i.e. in pure JS only) is much appreciated.

Answer 1

You shouldn't be doing things in a loop that don't depend on things changing in the loop. n < 2, n === 2, and n === 3 all depend on n, which is constant throughout your loop. Also, if you store your primes, you just have to loop through the primes until you get to sqrt(n), rather than checking every number. There are further tricks to speed up the algorithm, such as checking n only if n mod 60 is in [7,11,13,17,23,29,31,37,41,43,47,49,53,59]; that reduces the number of n to check by more than 3/4.

Is tail recursion an option?

How large is your stack size? You can break recursion into subrecursion. For instance, suppose you have a function that recursively finds the nth to n+100th primes. Then you can have a recursive function than, when asked to find k primes, calls itself on k-101, then appends the k-100 to kth primes. You can then add another layer, and have something that does 10 primes at a time. Do this in binary rather than base 10, and you'll need 14 layers to get 10001 primes.

Answer 2

Seems like you've figured this out yourself already, but I'll state it for you to make it clear...

The idea behind functional programming is mainly to make things easier to read and maintain (by being "declarative"). Usually/often this is done at the expense of performance. For example, it's a whole lot faster to iterate thru an array with a for loop than with the forEach method. Project Euler (or anything involving large numbers or heavy processing) is probably not a good place to practice functional programming with Javascript.

That said, this problem in particular doesn't justify the use of more than one function anyway. Your algorithm is overly complicated.

function getNthPrime(n) {
	let primes = [2, 3, 5];
	const isPrime = num => {
		for (let n = 0; n < primes.length; n++) {
			if (num === primes[n]) return true;
			if (num % primes[n] === 0) return false;
		}
		return true;
	};
	for (var i = 3; primes.length < n; i++)
		if (isPrime(i) && primes.indexOf(i) === -1) primes.push(i);
	return primes.pop();
};

console.log(getNthPrime(10001));

Now, if you really wanna do complicated math stuff functionally, I suggest making your own library, that way you get the benefit of learning how to do it with "vanilla" JS and you get to use the functional approach at the same time. That's what I'm doing.