Maratona de Programação da SBC - ACM ICPC - 2017 - Despojados

divisoresDespojados.js

// 2. (Maratona de Programação da SBC – ACM ICPC – 2017) Despojados:
// Todo inteiro positivo pode ser escrito como um produto de potências de primos. Por 
// exemplo, 252 = 2^2 X 3^2 X 7. Um inteiro é despojado se pode ser escrito como um produto de 
// 
// dois ou mais primos distintos, sem repetição. Por exemplo, 6 = 2 × 3 e 14 = 2 × 7 são
// despojados, mas 28 = 2^2 × 7, 1, 17 não são despojados.
// Entrada
// A entrada consiste de uma única linha que contém um inteiro N (1 ≤ N ≤ 1012). 
// Saída
// Seu programa deve produzir uma única linha com um inteiro representando o número de
// divisores despojados de N.
// Exemplo:
// Entrada:
// 252
// Saída:
// 4

function getPrimes(maxN) {
  const len = maxN + 1;
  const isPrime = [];
  const primes = [];

  // Todos são primos até que mostre o contrário
  for(let i = 0; i < len; i++) {
    isPrime.push(true);
  }

  // 0 e 1 não são primos, por isso são ignorados (i >= 2)
  for(let i = 2; i < len; i++) {
    if (!isPrime[i]) continue;

    primes.push(i);

    // Marca todos os multiplos de "i" como não primo.
    // Ex: se "i" for igual a 3, marca 6, 9, 12, 15, 18, etc como não primo.
    for (let mult=2, j=i*2; j < len; j=i*(++mult)) {
      isPrime[j] = false;
    }
  }

  return primes;
}

// Verifica se um número é "despojado".
// Recebe "primes" como parâmetro para evitar que a
// lista de primos seja recalculada para cada dividor
function isValid(n, primes) {
  const maxDivisor = Math.ceil(Math.sqrt(n));

  if ((n <= 2) || primes.includes(n)) {
    return false;
  }

  // Verifica se "n" é um produto de dois ou mais primos distintos
  for (let i = 0; i < primes.length && n > 1; i++) {
    const prime = primes[i];

    // Verifica se "n" é divísível pelo número primo atual (resto 0 === false)
    if (!(n % prime)) {
      n /= prime;

      // Se ele ainda for divisível pelo número primo, falhou no teste
      if (!(n % prime)) {
        return false;
      }
    }
  }

  return true;
}

function run(n) {
  const maxN = 1012;
  const primes = getPrimes(maxN);
  const validNumbers = [];

  for (let i = 2; i <= n; i++) {
    // Verifica se "i" é divisor de "n".
    // Se resto for diferente de zero, continua.
    if (n % i) continue;

    // Verifica se "i", que é divisor de "n", é um número despojado
    if (isValid(i, primes)) {
      validNumbers.push(i);
    }
  }

  return validNumbers;
}

console.log(run(252))