Как посчитать числа кратные двум числам?

Question

[Raul Abdullin]

Всем привет, совсем позабыл математику :)
Задача: как посчитать числа кратные двум числам?
А именно, для чисел 1920 и 600.
Пример: 60 делится и на 1920 и на 600.

Comments

[protven]

Пример: 60 делится и на 1920 и на 600.

Что ?

[Raul Abdullin]

protven: Не так выразился :) 1920 и 600 делится на 60 :)

Answer 1

[Александр Ручкин]

Разложите на множители
1920 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 3 * 5
600 = 2 * 2 * 2 * 3 * 5 * 5

Общие множители: 2, 2, 2, 3, 5
Сколько можно составить чисел из них, перемножая? Двойку можно взять от нуля до 3-х раз, т.е. 4 способа. Для 3 и 5 - по два способа (взять или не брать), итого 4 * 2 * 2 = 16 чисел, включая число 1 (все множители берём 0 раз).
Вот эти числа: 1, 2, 2*2, 2*2*2, 3, 3*2, 3*2*2, 3*2*2*2, 5, 5*2, 5*2*2, 5*2*2*2, 3*5, 3*5*2, 3*5*2*2, 3*5*2*2*2.

Comments

[Raul Abdullin]

Большое спасибо!

Answer 2

[Rsa97]

60 не делится ни на 1920, ни на 600. А вот 1920 и 600 делятся нацело на 60.
Судя по всему, вам нужен алгоритм НОД (наибольший общий делитель).

Comments

[Raul Abdullin]

Да, спасибо, я неправильно выразил свою мысль. Почитал информацию по вашей ссылке, но так и не понял, как вычислить все возможные делители для этих двух чисел. Возможно встречали какие-то ресурсы или приложение, в которые забиваешь два числа и выводят всевозможные комбинации?

[Rsa97]

raulvodov: Чтобы найти все возможные общие делители надо сначала найти НОД, затем разложить его на простые сомножители и взять все возможные комбинации произведений этих множителей.

НОД по бинарному алгоритму:

НОД(1920, 600) = 2*НОД(960, 300) = 4*НОД(480, 150) =
8*НОД(240, 75) = 8*НОД(120, 75) = 8*НОД(60, 75) =
8*НОД(30, 75) = 8*НОД(15, 75) = 8*НОД(30, 15) =
8*НОД(15, 15) = 8*15 = 120

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

120 = 2*60 = 2*2*30 = 2*2*2*15 = 2*2*2*3*5 = 5¹*3¹*2³

Перебираем возможные варианты (степени от 0 до максимальной):

5⁰*3⁰*2⁰ = 1
5⁰*3⁰*2¹ = 2
5⁰*3⁰*2² = 4
5⁰*3⁰*2³ = 8
5⁰*3¹*2⁰ = 3
5⁰*3¹*2¹ = 6
5⁰*3¹*2² = 12
5⁰*3¹*2³ = 24
5¹*3⁰*2⁰ = 5
5¹*3⁰*2¹ = 10
5¹*3⁰*2² = 20
5¹*3⁰*2³ = 40
5¹*3¹*2⁰ = 15
5¹*3¹*2¹ = 30
5¹*3¹*2² = 60
5¹*3¹*2³ = 120

[Raul Abdullin]

Rsa97: Огромное спасибо

Answer 3

[alexey230605]

это 9600
9600/1920=5
9600/600=16
разложите на простые множители, умножьте большее число на те простые множ., которые отсуттвуют в б. числе, но есть в м.
Для проверки разделите на НОД (наибольший общий делитель.)
Нахожд. НОД:
показываю на 13 и 17
17, 13, 4, 1, 0
предыд. перед 0 - 1