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

Число 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

Змінні:

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

n – перше натуральне число (цілого типу)
m – друге натуральне число (цілого типу )

Алгоритм

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

Програма

#include <iostream>
using namespace std;
int main()
{
    int n, m;  // n, m - вхідні числа для знаходження НСД
    cin >> n >> m;  // Введення двох чисел
    
    // Алгоритм Евкліда для знаходження НСД
    while (n != m)  // Поки числа не рівні
    {
        if (n > m) 
        {
            n = n - m;  // Віднімаємо менше число від більшого
        }
        else 
        {
            m = m - n;  // Віднімаємо менше число від більшого
        }
    }
    
    cout << n;  // Виведення результату (НСД)
    return 0;
}

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

Знайдіть найменше спільне кратне (НСК) за формулою .
Знайдіть найменше спільне кратне (НСК) за формулою .
Дано два цілих числа. З’ясуйте, чи вони взаємно прості.
Дано два цілих числа. З’ясуйте, чи вони взаємно прості.
Дано натуральні числа a і b, що позначають чисельник та знаменник простого дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, що . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
Дано натуральні числа a і b, що позначають чисельник та знаменник простого дробу. Скоротіть дріб, тобто знайдіть такі натуральні числа p та q, що не мають спільних дільників, що . Пояснення: за алгоритмом Евкліда знаходимо НСД(a,b) та ділимо чисельник та знаменник на це число.
Знайдіть суму двох простих дробів. Тобто дано натуральні числа a, b, c, d. Потрібно знайти два взаємно простих числа p і q, таких що . Пояснення: скласти два дробу. Чисельник дорівнює a*d+b*c. Знаменник дорівнює b*d. Потім за алгоритмом Евкліда знаходимо НСД чисельника та знаменника та ділимо чисельник та знаменник на це число.
Знайдіть суму двох простих дробів. Тобто дано натуральні числа 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) та алгоритм Евкліда. Пояснення: числа вводити у циклі, ввести два числа, знайти для них НСД, ввести третє число, знайти НСД для третього числа та знайденого НСД перших двох чисел, ввести четверте число і т.д. поки не будуть введені всі числа.

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