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

Основна теорема арифметики стверджує, що будь-яке натуральне число, більше одиниці, можна представити у вигляді добутку простих чисел, причому єдиним способом (якщо не враховувати їх порядок). Наприклад число 125 можна представити як де 5 — просте число. Нагадаємо, що розкладання чисел на добуток простих множників, називається їх факторизацією.

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

// Програма для знаходження розкладання заданого числа на прості множники
import java.util.Scanner;
class Decomposition_by_factors {
public static void main (String args[]) {
Scanner scann = new Scanner(System.in);
// ВВвід числа, розкладання якого необхідно отримати
System.out.print("Enter a number to decompose: ");
int num = scann.nextInt();
int c_num = num;
int n = 0;
int i = 2;
int table[] = new int[num + 1];
int dec[] = new int[num + 1];
// Побудова таблиці простих чисел
table = Sieve_of_eratosthenes(num);
// Знаходження розкладання заданого числа на прості множники
while (num > 1) {
if (table[i] != 0) {
while (num % table[i] == 0) {
num = num / table[i];
dec[n] = table[i];
n++;
}
}
i++;
}
// Вивід результатів роботи програми
System.out.print(c_num  + " =  "+ dec[0]);
for (int j = 1; i <= n - 1; j++) {
System.out.print(" *  " + dec[j]);
}
System.out.print(";");
}

Для побудови таблиці простих чисел, що не перевищують заданого числа, в програмі визначено додатковий методу Sieve_of_eratosthenes — повертає необхідний нам результат у вигляді масиву.

// Генерація простих чисел використовуючи решето Ератосфена
static int[] Sieve_of_eratosthenes (int n) {
// Оголошення та ініціалізація масиву розмірності n
int numbers[] = new int[+ 1];
// Заповнення масиву значеннями
for (int i = 1; i <= n; i++) {
numbers[i] = i;
}
// Викреслюємо в масиві складені числа
int prime = 2;
while (prime <= Math.floor(Math.sqrt(n))) {
int j = prime * prime;
while (j <= n) {
numbers[j] = 0;
j = j + prime;
}
for (int i = prime + 1; i <= n; i++) {
if (numbers[i] != 0) {
prime = i;
break;
}
}
}
return numbers;
}
}

Скомпілювавши, запустивши та задавши в якості числа, розкладання якого необхідно отримати, наприклад, значення 1260, на екрані відобразиться наступний результат:

Розкладання на множники Java

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

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар