Первичная факторизация факториала - PullRequest
Новая
       16

Первичная факторизация факториала

0 голосов
/ 23 мая 2019

Можно ли найти простые факторы факториала без фактического вычисления факториала ?

Моя точка зрения здесь состоит в том, чтобы найти простые множители факториала не большого числа. Ваш алгоритм должен пропустить этап вычисления факториала и вывести простые множители из n! где n <= 4000. </p>

Вычислить факториал и найти его простые делители довольно легко, но моя программа падает, когда ввод больше n = 22. Поэтому я подумал, что было бы довольно удобно выполнить весь процесс без вычисления факториала. 

function decomp(n){
  var primeFactors = [];
  var fact = 1;

  for (var i = 2; i <= n; i++) {
     fact = fact * i;
  }

  while (fact % 2 === 0) {
    primeFactors.push(2);
    fact = fact/2;
  }

  var sqrtFact = Math.sqrt(fact);
    for (var i = 2; i <= sqrtFact; i++) {
    while (fact % i === 0) {
      primeFactors.push(i);
      fact = fact/i;
      }
  }

   return primeFactors;
}

Я не ожидаю ни кода, ни ссылок, ни примеров, ни краткого описания.

1 Ответ

1 голос
/ 23 мая 2019

Давайте рассмотрим пример: 10! = 2 ^ 8 * 3 ^ 4 * 5 ^ 2 * 7 ^ 1. Я вычислил это, вычисляя факторы каждого числа от 2 до 10: 

 2: 2
 3: 3
 4: 2,2
 5: 5
 6: 2,3
 7: 7
 8: 2,2,2
 9: 3,3
10: 2,5

Тогда я просто посчитал каждый фактор. Есть восемь 2 (1 в 2, 2 в 4, 1 в 6, 3 в 8 и 1 в 10), четыре 3 (1 в 3, 1 в 6 и 2 в 9), два 5 (1 в 5 и 1 в 10) и один 7 (в 7).

С точки зрения написания программы, просто сохраните массив счетчиков (он должен иметь размер, равный квадратному корню из наибольшего факториала, который вы хотите разложить), и для каждого числа от 2 до факториала добавьте подсчет его факторов в массив счетчиков.

Это помогает?

...