How can I make this code more functional in Javascript?

Question

This code solves the problem of finding the in anth prime between 0 and 10,000:

  function PrimeMover(num) { 

  var counter = 0;
  var primes = [];

  for (var i=2; i<=10000; i++){

    for (var j = 2; j<i; j++){

      if (i%j===0) { counter++ };

    }

    if (counter === 0) { primes.push(i) };
    counter = 0;

  }

  return primes[num-1]

}

I would like a help, on how to solve the problem using Javascript functional programming.

Answer 1

The suggestion I would make is to make a sieve of erastostenes instead of an algorithm of "trial Division"

function PrimeMover(num) { 

  var N = 10000;
  var isPrime = [];
  isPrime[0] = false;
  isPrime[1] = false;
  for (var i=2; i <= N; i++){
      isPrime[i] = true;
  }

  var primes = [];
  for (var i=2; i <= N; i++){
    if(!isPrime[i]) continue;

    primes.push(i);
    for (var j = 2*i; j <= N; j += i){
      isPrime[i] = false;
    }
  }

  return primes[num-1]
}

This algorithm is much more efficient than the one you are using. It has complexity O(N log log N) while the algorithm for testing divisors has complexity O((N/log n)^2)

As for making the code more functional, I’m not sure it’s worth it. It is non-trivial to write the erastostenes sieve without using a vector and most functional algorithms to calculate primes you see around are inefficient like the code of your question: http://cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 2

The question ends up involving more mathematics than programming itself, as I am no expert in mathematics I will try to explain in the simplest and most lay way.

How to find out if a number is cousin? Simple, can only be divisible by 1 by itself.

Instead of following this rule why not look for numbers that are divisible by some number other than 1 and yourself? From here you already eliminate half the numbers up to their value.

Your possible divisors will have the following formula:

To implement:

function PrimeMover(num) {
    var encontrados = 1;
    var primos = [2];

    // já temos o [2] então posso partir do [3]
    var numero = 3; 

    // vai rodar quantas vezes forem necessárias até encontrar o enésimo número
    while (encontrados < num) {
        var numeroPrimo = true;

        // implementação da nossa regra, procura pelos valores até metade
        for (i=2; i <= Math.sqrt(numero); i++) {
            if (numero % i == 0) {
                numeroPrimo = false;
                break;
            }
        }

        // se for numero primo adiciona na lista e incrementa os encontrados pra saber quando parar
        if (numeroPrimo) {
            primos.push(numero);
            encontrados++;
        }
        numero++;
    }

    return primos[num-1];
}

Answer 3

The main concepts of the functional paradigm are high-order functions (functions that receive other functions such as arguments) and no side effects. Programs are written as compositions of functions, rather than sequential procedures.

To solve this problem, we can define the desired result as the list of numbers that passes a primality test.

We start by generating a list (an array, actually) of candidates:

var candidatos = [];
for (var i = 2; i <= 10000; i++) {
    candidatos.push(i);
}

And, of these candidates, we want to separate those who pass a primality test. We set our test:

var teste_primo = function (n) {
    for (var i=2; i*i <= n; i++)
    if (n%i == 0)
        return false;
    return true;
}

And finally, we filter from the candidates those who pass the test:

candidatos.filter(teste_primo)

Note that the function filter takes as argument another function - our primality test. It applies the test on the numbers and returns a new array containing only those that pass the test.

We can use the same function, for example, to separate the pairs:

candidatos.filter (function (n) {return n % 2 == 0})

(Note that I defined the function at the same time I passed it as a parameter - I don’t need to give it a name if I use it only once, which is common in the functional paradigm).

It is important to note that, except for the declaration of our list of candidates, none of our functions generated side effects (alteration of external variables, etc.). We define functions and compose these functions to obtain the result as return.

Another consequence is that if we want to change our primality test to something more efficient, we just need to provide another function instead of prime test. The primality test is isolated from the rest of the logic of the program.

Finally, the function filter is already implemented in the language, but we could implement our own version. What it does is receive an array, a test, and returns an array of the elements that pass the test:

var meu_filter = function (arr, teste){
    var saida = []
    for (var i = 0; i <= arr.length; i++)
    if (teste(arr[i])){
        saida.push(i)
    }
    return saida
}

Testing:

< meu_filter(candidatos,teste_primo)
> Array [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 1219 mais… ]