Варіант 1
Знайдіть найменше спільне кратне (НСК) за формулою НСК(a, b) = a · b / НСД(a, b) .
↑ До вибору варіантаТема 5. Цикли з умовою
Віднімаємо менше число від більшого, доки вони не стануть рівними. Знаходимо НСД без переліку всіх дільників.
Побачити алгоритм у дії ↓Крок 1
Дільник числа ділить його без остачі. Наприклад, 6 є дільником 18, бо 18 % 6 = 0.
Дільники 18: 1, 2, 3, 6, 9, 18.
Дільники 24: 1, 2, 3, 4, 6, 8, 12, 24.
Числа називають взаємно простими, якщо їхній НСД дорівнює 1. Наприклад, НСД(9, 16) = 1. При цьому самі числа 9 і 16 не є простими.
Крок 2
Поки два числа різні, від більшого віднімаємо менше. Коли числа стануть рівними, будь-яке з них і буде їхнім НСД.
| Числа | Дія | Після дії |
|---|---|---|
| 18 і 24 | 24 − 18 = 6 | 18 і 6 |
| 18 і 6 | 18 − 6 = 12 | 12 і 6 |
| 12 і 6 | 12 − 6 = 6 | 6 і 6 |
Отримали однакові числа. Отже, НСД(18, 24) = 6.
Спільні дільники двох чисел не змінюються, якщо від більшого відняти менше. Наприклад, дільники, спільні для 24 і 18, також спільні для 18 і 6. Обидва числа залишаються додатними, а їхня сума щоразу зменшується, тому повторення завершаться.
Крок 3
Введи два натуральні числа й натискай «Одне віднімання». Смужки показують, як зменшуються поточні числа.
Для наочності тренажер приймає числа від 1 до 100.
| Крок | Дія | x | y |
|---|
Спробуй 12 і 12: числа рівні від початку, тому віднімання взагалі не потрібні. Спробуй 9 і 16: у кінці обидва числа стануть рівними 1.
Крок 4
Введені a і b зберігаємо. Змінюємо лише їхні копії x та y, щоб початкові числа залишилися доступними після циклу.
#include <iostream>
using namespace std;
int main() {
int a, b, x, y;
cin >> a >> b;
x = a;
y = b;
while (x != y) {
if (x > y) {
x = x - y;
} else {
y = y - x;
}
}
cout << x;
return 0;
}Для 18 24 програма виведе 6, для 9 16 виведе 1. Вводимо додатні числа, що вміщуються в int.
!=, а рівність для перевірки як ==.Спосіб із відніманням простий, але для дуже різних чисел може потребувати багато повторень. Для навчальних прикладів обирай невеликі числа.
Крок 5
| Мета | Що робимо після знаходження g = НСД(a, b) |
|---|---|
| Перевірити взаємну простоту | Перевіряємо g == 1 |
| Скоротити дріб a / b | Новий чисельник a / g, знаменник b / g |
| Знайти НСК | (a / g) * b |
| Знайти НСД трьох чисел | Спочатку НСД(a, b), потім НСД отриманого результату та c |
Наприклад, дріб 18/24 скорочується на 6: отримаємо 3/4. Найменше спільне кратне 18 і 24: (18 / 6) · 24 = 72.
У формулі НСК краще спочатку поділити, а потім помножити. Для добутків і додавання дробів використовуй невеликі значення або цілий тип long long, який вміщує більші числа.
Крок 6
Варіанти 3 і 4 задані для цілих чисел. Від’ємні значення спочатку заміни на протилежні, наприклад: if (x < 0) x = -x;. Використовуй невеликі вхідні значення.
Нульові значення перевір окремо до запуску віднімання: якщо лише одне число дорівнює 0, пара взаємно проста тільки тоді, коли модуль іншого дорівнює 1. Пара 0 і 0 не є взаємно простою.
Для варіантів з інтервалами в цьому уроці використовуй натуральні межі та додатне число для порівняння. Кінці інтервалів включаємо. У варіантах із парами виводь кожну пару один раз, беручи перше число меншим за друге.
Щоб скоротити дріб, чисельник і знаменник потрібно поділити на їхній НСД. Формулювання «не мають спільних дільників» слід розуміти як «не мають спільних дільників, крім 1».
Крок 7
Нумерацію й повторювані варіанти збережено.
Знайдіть найменше спільне кратне (НСК) за формулою НСК(a, b) = a · b / НСД(a, b) .
↑ До вибору варіантаЗнайдіть найменше спільне кратне (НСК) за формулою НСК(a, b) = a · b / НСД(a, b) .
↑ До вибору варіантаДано два цілих числа. З’ясуйте, чи вони взаємно прості.
↑ До вибору варіантаДано два цілих числа. З’ясуйте, чи вони взаємно прості.
↑ До вибору варіантаДано натуральні числа a і b, що позначають чисельник та знаменник звичайного дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, крім 1, і задовольняють рівність a / b = p / q . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
↑ До вибору варіантаДано натуральні числа a і b, що позначають чисельник та знаменник звичайного дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, крім 1, і задовольняють рівність a / b = p / q . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
↑ До вибору варіантаЗнайдіть суму двох звичайних дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких, що a / b + c / d = p / q. Пояснення: додати два дроби. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.
↑ До вибору варіантаЗнайдіть суму двох звичайних дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких, що a / b + c / d = p / q. Пояснення: додати два дроби. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.
↑ До вибору варіантаЗнайдіть найбільший спільний дільник трьох натуральних чисел за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).
↑ До вибору варіантаЗнайдіть найбільший спільний дільник трьох натуральних чисел за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).
↑ До вибору варіантаДано числа A, B, C. Знайдіть в інтервалі [A, B] усі числа взаємно прості з C.
↑ До вибору варіантаДано числа M, N, R. Знайдіть в інтервалі [M, N] усі числа взаємно прості з R.
↑ До вибору варіантаЗнайдіть усі пари взаємно простих чисел в інтервалі [A, B]
↑ До вибору варіантаЗнайдіть усі пари взаємно простих чисел в інтервалі [M, N]
↑ До вибору варіантаЗнайдіть всі правильні звичайні дроби, що не скорочуються, знаменники яких не більше 5 (дріб задається двома натуральними числами; чисельником та знаменником). Відповідь: 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5
↑ До вибору варіантаЗнайдіть всі правильні звичайні дроби, що не скорочуються, знаменники яких не більше 7 (дріб задається двома натуральними числами; чисельником та знаменником). Відповідь: 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7
↑ До вибору варіантаДано натуральні числа m, n1, n2, ...,nm (m>=2). Обчисліть НСД(n1,n2,...,nm ), використовуючи співвідношення НСД(n1,n2,...,nm)=НСД(НСД(n1,n2,...,nm-1),nm) та алгоритм Евкліда. Пояснення: числа вводити у циклі, ввести два числа, знайти для них НСД, ввести третє число, знайти НСД для третього числа та знайденого НСД перших двох чисел, ввести четверте число і т.д. поки не будуть введені всі числа.
↑ До вибору варіанта