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

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

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

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

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

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

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

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

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