Решето Ератосфена — метод пошуку простих чисел

Як ми вже встигли переконатись, не всі числа важко ідентифікувати як прості або складені. Наприклад, будь-яке парне число більше 2 є складеним. Однак, хоча деякі числа можуть бути легко класифіковані, для інших дана процедура може бути надзвичайно складною. На щастя, є деякі прийоми, які дозволяють значно спростити процес відшукання простих чисел. Одним з таких прийомів є сито Ератосфена — математичний інструмент, який використовується для виявлення всіх можливих простих чисел між будь-якими двома числами. Метою цього параграфу є максимально ефективна реалізація даного алгоритму засобами Java, не вдаючись до імпорту будь-яких стандартних бібліотек.

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

// Програма для генерації простих чисел використовуючи решето Ератосфена
import java.util.Scanner;
class Sieve_of_eratosthenes {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// Ввід кінця діапазону
System.out.print("Enter end of range: ");
int end = scann.nextInt();

Далі, оголошуємо та виділяємо пам'ять під масив з числами цілого типу і, простим присвоюванням в циклі (починаючи з двійки і закінчуючи кінцем діапазону) виконуємо запис значень в його комірки.

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

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

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

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

Після того, як з вхіднимим даними розібрались, обчислюємо добуток чисел number1 і number2 та реалізуємо процес знаходження НСД за алгоритмом Евкліда.

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

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

Нагадаємо, що у параграфі найбільший спільний дільник (НСД), нами було сформульовано означення та розглянуто основні методи знаходження НСД. На продовження даної теми, сьогодні буде створена 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 даний процес виглядатиме наступним чином:

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

Розкладання чисел на прості множники

Нагадаємо, що цілі додатні числа більші за одиницю діляться на прості та складені. Різниця між ними полягає в числі дільників. Просте число має два натуральних дільники — одиницю та самого себе. Наприклад, 2, 3, 5, 7, 11,... (одиниця не є простим числом). Число, яке має більше ніж два натуральних дільники, називається складеним. Зазначимо, що будь-яке складене число можливо представити як добуток простих чисел. Наприклад, число 20 можна представити як , де 2 та 5 — прості числа. Саме таке представлення і називається розкладанням чисел на прості множники.

Зазначимо, що складене число розкладається на прості множники єдиним чином. Це означає, що якщо, наприклад, число 20 розклалося на дві двійки і одну п'ятірку, то воно завжди буде так розкладатися незалежно від того, почнемо ми розкладання з малих множників чи з великих. Прийнято починати розкладання з малих множників, тобто з двійок, трійок і так далі. Це зручніше тому, що про подільність числа на 2, на 3, на 5 легше судити, ніж про його подільність, наприклад, на число 59 чи 67.

Два способи отримання одного розкладання

Знову-таки повертаючись до нашого прикладу, бачимо, що для невеликих чисел здогадатися яким буде їх розкладання доволі легко. Виникає питання, яким же чином виконується розкладання на множники великих чисел? Зазначимо, що тут нам допоможуть ознаки подільності та таблиця простих чисел. Покажемо, як за їх допомогою отримати розкладання деякого натурального складеного числа .

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

Знаходження простих чисел використовуючи решето Ератосфена

Просте число — натуральне ціле додатне число, що має рівно два різних натуральних дільники — одиницю і самого себе. Іншими словами, число є простим, якщо воно більше одиниці і при цьому ділиться без залишку тільки на 1 та на . Наприклад, 3 — просте число, а число 6 ні — крім 1 та 6, також ділиться на 2 і на 3.

Таблиця простих чисел до 1000

Натуральні числа, які являються більшими одиниці і не є простими, називаються складеними. Таким чином, всі натуральні числа розбиваються на три класи: одиницю (має один натуральний дільник), прості числа (мають два натуральних дільники) і складені числа (мають більше двох натуральних дільників).

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

Знаходження центру графа (реалізація в середовищі Delphi)

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

Для того, щоб запустити програму необхідно перейти в каталог де він збережений, знайти файл Project.exe і запустити його. Після запуску програми на екрані буде відображено вікно наступного вигляду:

Головне вікно проекту "Знаходження центру графа"

У верхній частині форми розташовується панель інструментів. На панелі розташовується чотири кнопки (дві типу TSpeedButton та дві — TButton) зліва направо: «Додати вершину», «Додати ребро», «Видалити граф», «Знайти центр графа». Праворуч від кнопки «Додати ребро» міститься перемикач типу TCheckBox, який відповідає за тип створюваного ребра (якщо перемикач не включений, то програма пряцює в режимі «Розміщення орієнтованого ребра», і навпаки, якщо перемикач включений — в режмрі «Розміщення неорієнтованого ребра». Біла область (компонент типу TImage) називається робочою областю і використовується для візуалізації графа та відображення вершини, яка являється центральною. Нижня частина форми (компонент типу TMemo) призначена для виводу результатів роботи програми.

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

Наступна сторінка »