Условие задачи
Найдите все делители натурального числа $n$.
Входные данные
Одно натуральное число $ n ( n \leqslant 10^9 ) $.
Выходные данные
Выведите в возрастающем порядке все делители числа $n$.
Тесты
| № | Входные данные | Выходные данные |
|---|---|---|
| 1 | 10 | 1 2 5 10 |
| 2 | 36 | 1 2 3 4 6 9 12 18 36 |
| 3 | 455 | 1 5 7 13 35 65 91 455 |
| 4 | 38965 | 1 5 7793 38965 |
| 5 | 999999 | 1 3 7 9 11 13 21 27 33 37 39 63 77 91 99 111 117 143 189 231 259 273 297 333 351 407 429 481 693 777 819 999 1001 1221 1287 1443 2079 2331 2457 2849 3003 3367 3663 3861 4329 5291 6993 8547 9009 10101 10989 12987 15873 25641 27027 30303 37037 47619 76923 90909 111111 142857 333333 999999 |
| 6 | 1000000000 | 1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); double sqrt_n = Math.sqrt (n); for (int i = 1; i < sqrt_n; i++) { if (n % i == 0) System.out.print(i + " "); } for (int i = (int)sqrt_n; i >= 1; i--) { if (n % i == 0) System.out.print(n/i + " "); } } } |
Решение
Можно заметить, что делитель и частное взаимодополняют друг друга. Мы найдем делители, потом частные этого выражения. Так как частные также являются делителями. Значит последовательность делителей в порядке возрастания можно разделить на две части. Создадим два цикла для нахождения этих двух частей:
- в первом цикле проверяем каждое натуральное число от $1$ до $\sqrt n$. Выводим числа, если они являются делителями;
- во втором цикле делим заданное число $n$ на все делители и выводим.
Ссылки
Условие задачи на E-olymp
Код на Ideone
Засчитанный код на E-olymp