Условие задачи
Вывести представление целого числа $n$ в виде произведения простых чисел.
Входные данные
Единственное число $n (2 \leq n \leq 2^{31} — 1).$
Выходные данные
Вывести список простых множителей в порядке неубывания, разделённых знаком «$*$».
Тесты
| Входные данные | Выходные данные |
|---|---|
30 |
2*3*5 |
16 |
2*2*2*2 |
5 |
5 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); long numb, divisor = 2; numb = Integer.parseInt(params1[0]); while (divisor*divisor <= numb) { if (numb%divisor == 0) { System.out.print(divisor); numb = numb / divisor; System.out.print('*'); } else if (divisor == 2) divisor = 3; else divisor = divisor + 2; } System.out.print(numb); } } |
Решение задачи
Пока наше число больше либо равно
divisor*divisor выполняется:
- Если numb делится нацело на divisor, мы выводим наш делитель, следовательно numb делится на divisor;
- В противном случае:
- Если divisor равен $2$ , то присваиваем ему значение $3$ и повторяем;
- В другом случае увеличиваем его на $2$;
Таким образом перебираются $2$,$3$ и $5$, которые являются делителем для всех чисел.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone