Разложение числа на множители

Будем раскладывать скажем число 360 на множители простым способом:

Итак, смотрим на что делится 360, а делится оно на: 2, 3, 5, 9, 10. Из этих чисел выбираем, которое больше нравится (мну нравится 3, она же неофициальная "зю") и делим на него:

360 / 3 = 120

Повторяем ситуацию с числом 120, оно делится на 2, 3, 5. Возьмем теперь эдак 5:

120 / 5 = 24

Смотрим, делится на 2, 3 возьмем 3

24 / 3 = 8

Ну и остается три раза на 2 поделить восемь:

8 / 2 = 4
4 / 2 = 2
2 / 2 = 1

Теперь выписываем все, на что мы делили и получаем: 2, 2, 2, 3, 5, 3 и ежели это перемножить - то получим исходное число 360.

Спрашивается: вот к чему вообще оно надо это разложение?

Конечно же для того, что бы взломать Криптосистему RSA! Вон оно оказывается чему в школе учат. :) Правда тут для разложения используют "Функцию Эйлера", которую я вспомню позднее.

Ну и еще это все надо для того, что бы найти "Наибольший общий делитель"(НОД) и "Наименьшее общее кратное"(НОК)

НОД

Возьмем два числа 360 и 420, разложим их и будем высматривать нечто одинаковое:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

Теперь это одинаковое просто перемножим:

2 * 2 * 3 * 5 = 60

Выходит наибольший общий делитель это число 60.

НОК

Чтобы найти НОК - так же разложим число 360 и 420, только на этот раз добавим одному из них недостающие члены:

360 = 2*2*2*3*3*5
420 = 2*2*3*5*7

НОК = 2*2*3*5*7*2*3 = 2520

Проверка:

360 * 420 = НОД(60) * НОК(2520)
151200 = 151200

Вот все и сошлось.