Делители числа 500000004

Задача: найдите все делители числа 500000004.

Решение:

Делителем числа 500000004 называют натуральное число на которое 500000004 делится без остатка. Для нахождения всех делителей воспользуемся следующим алгоритмом:

• разложим 500000004 на простые множители;
• найдём все возможные произведения полученных множителей (перемножим полученные значения между собой) и добавим их к ранее найденным;
• добавим единицу (т.к. единица является делителем любого числа).

Таким образом:

1. Раскладываем 500000004 на простые множители:

500000004 = 2² · 3² · 7 · 109² · 167

Подробнее о том, как расскладывать число на простые множители, смотрите тут.

2. Перемножим между собой полученные множители (2, 2, 3, 3, 7, 109, 109, 167). Получаем:

2 · 2 = 4
2 · 3 = 6
2 · 2 · 3 = 12
3 · 3 = 9
2 · 3 · 3 = 18
2 · 2 · 3 · 3 = 36
2 · 7 = 14
2 · 2 · 7 = 28
3 · 7 = 21
2 · 3 · 7 = 42
2 · 2 · 3 · 7 = 84
3 · 3 · 7 = 63
2 · 3 · 3 · 7 = 126
2 · 2 · 3 · 3 · 7 = 252
2 · 109 = 218
2 · 2 · 109 = 436
3 · 109 = 327
2 · 3 · 109 = 654
2 · 2 · 3 · 109 = 1308
3 · 3 · 109 = 981
2 · 3 · 3 · 109 = 1962
2 · 2 · 3 · 3 · 109 = 3924
7 · 109 = 763
2 · 7 · 109 = 1526
2 · 2 · 7 · 109 = 3052
3 · 7 · 109 = 2289
2 · 3 · 7 · 109 = 4578
2 · 2 · 3 · 7 · 109 = 9156
3 · 3 · 7 · 109 = 6867
2 · 3 · 3 · 7 · 109 = 13734
2 · 2 · 3 · 3 · 7 · 109 = 27468
109 · 109 = 11881
2 · 109 · 109 = 23762
2 · 2 · 109 · 109 = 47524
3 · 109 · 109 = 35643
2 · 3 · 109 · 109 = 71286
2 · 2 · 3 · 109 · 109 = 142572
3 · 3 · 109 · 109 = 106929
2 · 3 · 3 · 109 · 109 = 213858
2 · 2 · 3 · 3 · 109 · 109 = 427716
7 · 109 · 109 = 83167
2 · 7 · 109 · 109 = 166334
2 · 2 · 7 · 109 · 109 = 332668
3 · 7 · 109 · 109 = 249501
2 · 3 · 7 · 109 · 109 = 499002
2 · 2 · 3 · 7 · 109 · 109 = 998004
3 · 3 · 7 · 109 · 109 = 748503
2 · 3 · 3 · 7 · 109 · 109 = 1497006
2 · 2 · 3 · 3 · 7 · 109 · 109 = 2994012
2 · 167 = 334
2 · 2 · 167 = 668
3 · 167 = 501
2 · 3 · 167 = 1002
2 · 2 · 3 · 167 = 2004
3 · 3 · 167 = 1503
2 · 3 · 3 · 167 = 3006
2 · 2 · 3 · 3 · 167 = 6012
7 · 167 = 1169
2 · 7 · 167 = 2338
2 · 2 · 7 · 167 = 4676
3 · 7 · 167 = 3507
2 · 3 · 7 · 167 = 7014
2 · 2 · 3 · 7 · 167 = 14028
3 · 3 · 7 · 167 = 10521
2 · 3 · 3 · 7 · 167 = 21042
2 · 2 · 3 · 3 · 7 · 167 = 42084
109 · 167 = 18203
2 · 109 · 167 = 36406
2 · 2 · 109 · 167 = 72812
3 · 109 · 167 = 54609
2 · 3 · 109 · 167 = 109218
2 · 2 · 3 · 109 · 167 = 218436
3 · 3 · 109 · 167 = 163827
2 · 3 · 3 · 109 · 167 = 327654
2 · 2 · 3 · 3 · 109 · 167 = 655308
7 · 109 · 167 = 127421
2 · 7 · 109 · 167 = 254842
2 · 2 · 7 · 109 · 167 = 509684
3 · 7 · 109 · 167 = 382263
2 · 3 · 7 · 109 · 167 = 764526
2 · 2 · 3 · 7 · 109 · 167 = 1529052
3 · 3 · 7 · 109 · 167 = 1146789
2 · 3 · 3 · 7 · 109 · 167 = 2293578
2 · 2 · 3 · 3 · 7 · 109 · 167 = 4587156
109 · 109 · 167 = 1984127
2 · 109 · 109 · 167 = 3968254
2 · 2 · 109 · 109 · 167 = 7936508
3 · 109 · 109 · 167 = 5952381
2 · 3 · 109 · 109 · 167 = 11904762
2 · 2 · 3 · 109 · 109 · 167 = 23809524
3 · 3 · 109 · 109 · 167 = 17857143
2 · 3 · 3 · 109 · 109 · 167 = 35714286
2 · 2 · 3 · 3 · 109 · 109 · 167 = 71428572
7 · 109 · 109 · 167 = 13888889
2 · 7 · 109 · 109 · 167 = 27777778
2 · 2 · 7 · 109 · 109 · 167 = 55555556
3 · 7 · 109 · 109 · 167 = 41666667
2 · 3 · 7 · 109 · 109 · 167 = 83333334
2 · 2 · 3 · 7 · 109 · 109 · 167 = 166666668
3 · 3 · 7 · 109 · 109 · 167 = 125000001
2 · 3 · 3 · 7 · 109 · 109 · 167 = 250000002
2 · 2 · 3 · 3 · 7 · 109 · 109 · 167 = 500000004

3. Получаем 3 набора значений:

• 2, 3, 7, 109, 167 — простые числа из 1-го пункта;
• 4, 6, 12, 9, 18, 36, 14, 28, 21, 42, 84, 63, 126, 252, 218, 436, 327, 654, 1308, 981, 1962, 3924, 763, 1526, 3052, 2289, 4578, 9156, 6867, 13734, 27468, 11881, 23762, 47524, 35643, 71286, 142572, 106929, 213858, 427716, 83167, 166334, 332668, 249501, 499002, 998004, 748503, 1497006, 2994012, 334, 668, 501, 1002, 2004, 1503, 3006, 6012, 1169, 2338, 4676, 3507, 7014, 14028, 10521, 21042, 42084, 18203, 36406, 72812, 54609, 109218, 218436, 163827, 327654, 655308, 127421, 254842, 509684, 382263, 764526, 1529052, 1146789, 2293578, 4587156, 1984127, 3968254, 7936508, 5952381, 11904762, 23809524, 17857143, 35714286, 71428572, 13888889, 27777778, 55555556, 41666667, 83333334, 166666668, 125000001, 250000002, 500000004 — произведения из 2-го пункта;
• 1 — единица, которая является делителем любого числа.

Объединяем и получаем делители для числа 500000004:

1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 109, 126, 167, 218, 252, 327, 334, 436, 501, 654, 668, 763, 981, 1002, 1169, 1308, 1503, 1526, 1962, 2004, 2289, 2338, 3006, 3052, 3507, 3924, 4578, 4676, 6012, 6867, 7014, 9156, 10521, 11881, 13734, 14028, 18203, 21042, 23762, 27468, 35643, 36406, 42084, 47524, 54609, 71286, 72812, 83167, 106929, 109218, 127421, 142572, 163827, 166334, 213858, 218436, 249501, 254842, 327654, 332668, 382263, 427716, 499002, 509684, 655308, 748503, 764526, 998004, 1146789, 1497006, 1529052, 1984127, 2293578, 2994012, 3968254, 4587156, 5952381, 7936508, 11904762, 13888889, 17857143, 23809524, 27777778, 35714286, 41666667, 55555556, 71428572, 83333334, 125000001, 166666668, 250000002, 500000004

Ответ:

• Делители числа 500000004: 1, 2, 3, 4, 6, 7, 9, 12, 14, 18, 21, 28, 36, 42, 63, 84, 109, 126, 167, 218, 252, 327, 334, 436, 501, 654, 668, 763, 981, 1002, 1169, 1308, 1503, 1526, 1962, 2004, 2289, 2338, 3006, 3052, 3507, 3924, 4578, 4676, 6012, 6867, 7014, 9156, 10521, 11881, 13734, 14028, 18203, 21042, 23762, 27468, 35643, 36406, 42084, 47524, 54609, 71286, 72812, 83167, 106929, 109218, 127421, 142572, 163827, 166334, 213858, 218436, 249501, 254842, 327654, 332668, 382263, 427716, 499002, 509684, 655308, 748503, 764526, 998004, 1146789, 1497006, 1529052, 1984127, 2293578, 2994012, 3968254, 4587156, 5952381, 7936508, 11904762, 13888889, 17857143, 23809524, 27777778, 35714286, 41666667, 55555556, 71428572, 83333334, 125000001, 166666668, 250000002, 500000004;
• Количество делителей: 108.