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

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

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