Как разложить число на множители

672

08 января 2017, 16:55

Не получается разложить число х на множители:

for (int i = 1; i <= x; i++) {
    if (x % i == 0) {
        a = i;
        System.out.print(a + " ")
    }
}

Answer 1

Берём проверяемое число (currentValue - копию числа, дабы не портить оригинал) и первый множитель (multiplier) равный 2.
Если проверяемое число кратно множителю, то выводим множитель на экран как подходящий, а проверяемое число делим на множитель.
Если множитель не подходит, то переходим к следующему множителю (+1 в случае 2 и +2 в других случаях).
Повторяем пункты 2 и 3 до тех пор, пока проверяемое значение больше 1, а множитель меньше квадратного корня из оригинального числа (sqrt).

Если проверяемое значение не равно 1 после цикла, то выводим его.

int x = 660;
double sqrt = Math.sqrt(x);
int currentValue = x;
int multiplier = 2;
while (currentValue > 1 && multiplier <= sqrt)
{
    if (currentValue % multiplier == 0)
    {
        System.out.print(multiplier + " ");
        currentValue /= multiplier;
    }
    else if (multiplier == 2)
    {
        multiplier++;
    }
    else
    {
        multiplier += 2;
    }
}
if (currentValue != 1)
{
    System.out.print(currentValue);
}

Answer 2

Это издевательство - перебирать все подряд...
Посмотрите, например, тут - недавний вопрос.

Я в Java не мастак, поэтому расскажу словами (на C++ - см. по приведенной ссылке).
Если не строить таблицу простых чисел, то
1. Пока N четно, делим на 2 и записываем 2 как один из делителей (их может быть несколько).
2. Теперь N нечетно. Начиная с 3, проверяем все нечетные числа, до квадратного корня из N (проверяя для простоты i*i <= N, а не вычисляя корень), на делимость. Если не делится ни на одно - выписываем последний простой множитель - само N, и завершаем работу.
3. Если делится - выписываем очередной делитель, делим на него N, и повторяем цикл из п.2 для нового значения N, начиная не с 3, а с последнего найденного делителя.

Вот, собственно, и все.