Назад Зміст Вперед

Задачі на знаходження НСД за алгоритмом Евкліда

Число n є дільником числа m, якщо число m ділиться на число n без остачі.

Дільники числа 18: 1, 2, 3, 6, 9, 18.

Дільники числа 24: 1, 2, 3, 4, 6, 12, 24.

Найбільший спільний дільник чисел 18 та 24 це 6. Скорочено: НСД (18, 24) = 6.

НСД (m, n) це найбільше з чисел на яке діляться і m і n.

Два числа m та n називаються взаємно простими, якщо їх НСД (m, n)=1. Наприклад, НСД(9, 16)=1. Не плутати з простими числами! Числа 9 та 16 не прості, бо мають дільники окрім 1 та самого числа.

Алгоритм Евкліда дозволяє знайти НСД двох натуральних чисел.

Суть алгоритму Евкліда – два числа порівнюють, та з більшого віднімають менше до тих пір, поки числа не стануть рівними. Число, якому вони стануть рівними і є їх найбільший спільний дільник.

Алгоритм Евкліда змінює вхідні дані! Тому рекомендується їх запам’ятовувати у інші змінні.

Приклад

Знайдіть НСД(n,m)найбільший спільний дільник двох натуральних чисел, за алгоритмом Евкліда.

Результат роботи програми

Ввід Вивід
18 24 6
9 16 1

Змінні:

Вхідні та вихідні:

Алгоритм

  1. Спочатку потрібно ввести числа n, m.
  2. Якщо числа не рівні потрібно з більшого віднімати менше, поки вони не стануть рівними. Тобто спочатку потрібно перевіряти умову, а потім змінювати числа. Тому будемо використовувати цикл while.
  3. У заголовку циклу перевіряється умова n!=m , числа не рівні?
  4. У тілі циклу будемо виконувати такі дії:
  5. Коли цикл закінчиться, тобто числа стають рівними (n=m)
  6. Виводимо на екран будь-яке з них.

Програма

Варіанти задач

  1. Знайдіть найменше спільне кратне (НСК) за формулою .
  2. Знайдіть найменше спільне кратне (НСК) за формулою .
  3. Дано два цілих числа. З’ясуйте, чи вони взаємно прості.
  4. Дано два цілих числа. З’ясуйте, чи вони взаємно прості.
  5. Дано натуральні числа a і b, що позначають чисельник та знаменник простого дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, що . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
  6. Дано натуральні числа a і b, що позначають чисельник та знаменник простого дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, що . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
  7. Знайдіть суму двох простих дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких що . Пояснення: скласти два дробу. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.
  8. Знайдіть суму двох простих дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких що . Пояснення: скласти два дробу. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.
  9. Знайдіть найбільший спільний дільник трьох натуральних чисел, за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).
  10. Знайдіть найбільший спільний дільник трьох натуральних чисел, за алгоритмом Евкліда та формулою НСД(a,b,c)=НСД(НСД(a,b),c).
  11. Дано числа A, B, C. Знайдіть в інтервалі [A, B] усі числа взаємно прості з C.
  12. Дано числа M, N, R. Знайдіть в інтервалі [M, N] усі числа взаємно прості з R.
  13. Знайдіть усі пари взаємно простих чисел в інтервалі [A, B]
  14. Знайдіть усі пари взаємно простих чисел в інтервалі [M, N]
  15. Знайти всі правильні прості дроби, що не скорочуються, знаменники яких не більше 5 (дріб задається двома натуральними числами – чисельником та знаменником). Відповідь: 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5
  16. Знайти всі правильні прості дроби, що не скорочуються, знаменники яких не більше 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
  17. Дано натуральні числа m, n1, n2, ...,nm (m>=2). Обчисліть НСД(n1,n2,...,nm ), використовуючи співвідношення НСД(n1,n2,...,nm)=НСД(НСД(n1,n2,...,nm-1),nm) та алгоритм Евкліда. Пояснення: числа вводити у циклі, ввести два числа, знайти для них НСД, ввести третє число, знайти НСД для третього числа та знайденого НСД перших двох чисел, ввести четверте число і т.д. поки не будуть введені всі числа.

Назад Зміст Вперед