Алгоритм Евкліда — знаходження найбільшого спільного дільника

Нагадаємо, що у параграфі найбільший спільний дільник (НСД), нами було сформульовано означення та розглянуто основні методи знаходження НСД. На продовження даної теми, сьогодні буде створена java-програма, яка допоможе швидко визначити найбільший спільний дільник двох додатних цілих чисел використовуючи алгоритм Евкліда. Зазначимо, що наша сьогоднішня програма не буде мати інтерфейсу. Всі дані передаватимуться через консоль.

Отже, для початку створимо «Java Project», потім в ньому створимо «Java Class» і назвемо його, наприклад, Greatest_common_divisor. На наступному кроці, виходячи з того, що для знаходження НCД , від користувача, нам знадобляться два числа number1 і number2, то для їх введення скористаємось класом Scanner з бібліотеки пакетів Java.

// Програма для знаходження найбільшого спільного дільника двох натуральних чисел (НСД)
import java.util.Scanner;
class Greatest_common_divisor {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// Ввід вхідних даних
System.out.print("Enter number1:");
int number1 = scann.nextInt();
System.out.print("Enter number2:");
int number2 = scann.nextInt();

Зазначимо, що для того, щоб не обтяжувати користувача зайвими турботами, ми дозволимо йому вводити числа в довільному порядку, хоча для алгоритму важливо, щоб перше число було більше другого. Тобто, будемо виправляти цю ситуацію програмно, якщо в цьому винекне необхідність.

Читати повністю

Найменше спільне кратне двох натуральних чисел

Кратним числа називається таке число, яке саме ділиться на  без залишку. Спільне кратне чисел і  — це число, що є кратним для кожного з них.

До прикладу, числа 10 і 15 мають спільне кратне 180. Числа 150, 120, 90 — також є спільними кратними цих чисел. Серед всіх спільних кратних завжди є найменше, в даному випадку таким являється число 30. Це число називають найменшим спільним кратним (НОК) і позначають .

Щоб знайти найменше спільне кратне двох чисел, потрібно розкласти їх на прості множники. Після цього, необхідно вибрати всі прості множник що входять в обидві множини та перемножити їх між собою. На наступному кроці, отриманий результат необхідно також помножити на прості множники, числа , які не являються множниками числа  та прості множникик числа , що не являються простими множниками числа . До прикладу, для чисел 441 та 350 даний процес виглядатиме наступним чином:

Читати повністю

Знаходження найбільшого спільного дільника за алгоритмом Евкліда

Кожен дільник натурального числа  не може бути більшим самого числа , тому число  має скінченне число дільників, які не перевищують .

Серед дільників чисел і  можуть бути однакові, тобто спільні дільники. Очевидно, їх кількість так само є скінченною. Наприклад, числа 30 і 70 мають чотири спільних дільники: 1, 2, 5 і 10. Серед цих дільників є найбільший (в даному випадку 10), його називають найбільшим спільним дільником (НСД) і позначають .

Отже, найбільшим спільним дільником двох натуральних чисел називається найбільше натуральне число, на яке ділиться кожне з цих чисел без залишку. З даного означення випливає, що для того, щоб знайти НСД двох чисел і , на першому кроці, необхідно знайти всі додатні дільники числа і всі додатні дільники числа . Далі, необхідно вибрати всі числа, що входять в обидві множини, та визначити найбільше серед них. Воно і буде найбільшим спільним дільником.

Читати повністю