Как написать программу, разлагающую число X на простые множители?

Question

[Никита Пиковец]

Это уже задачка посложнее.. Я думаю, что надо организовать цикл с массивом (массив состоит из таблицы простых чисел, их там где то 50).. но у меня как всегда ничего не получается..

Answer 1

[Rsa97]

Нужно получать все простые от 2 до sqrt(X), одновременно проверяя остаток от деления X на простое. Для небольших X можно сделать решетом Эратосфена, размер массива будет sqrt(X) для стандартной реализации решета, если отдельно исключить чётные и использовать в решете битовые маски, то можно уменьшить до sqrt(X)/16.

Answer 2

[bromzh]

Решение в лоб:

function f(number) {
	var result = [];
	var d = 2;
	while (number > 1) {
		if (number % d === 0) {
			number /= d;
			result.push(d);
			d = 2;
		} else {
			d++;
		}
	}
	return result;
}
// Результат работы
f(10); // -> [2, 5]
f(3559); // -> [3559]
f(123456); // -> [2, 2, 2, 2, 2, 2, 3, 643]
// Проверка
f(123321).reduce(function(a, b) { return a * b }); // -> 123321
f(200).reduce(function(a, b) { return a * b }) === 200; // -> true

Совсем кодеры обленились. Так трудно головой немного подумать?

Comments

[Никита Пиковец]

Буду думать)

Answer 3

[Andrii Votiakov]

function primeFactorization(num){
  var root = Math.sqrt(num),  
  result = arguments[1] || [], 
  x = 2; 
  
  if(num % x){
   x = 3;
   while((num % x) && ((x = x + 2) < root)){}
  }
  
  x = (x <= root) ? x : num;
  result.push(x);

 
  return (x === num) ? result : primeFactorization(num/x, result) ;
}

Проверить на jsfiddle

Comments

[Никита Пиковец]

Что делает эта строка?
result = arguments[1] || [],

[Andrii Votiakov]

primeFactorization(num/x, result) ; мы рекурсивно посылаем в функцию 2 аргумента, а считываем primeFactorization(num) один. result = arguments[1] || [] присваивает переменной result значение второго аргумента, который мы послали в функцию. Если второго элемента нет, мы создаем пустой массив result