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

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

🔢 Розкладіть будь-яке число на прості множники. Переглядайте результат у вигляді добутку, зі степенями, візуалізацією дерева множників та покроковим процесом ділення.

Що таке розклад на прості множники?

Розклад на прості множники (або факторизація цілих чисел) — це процес розбиття складеного числа на добуток простих чисел. Кожне складене число має єдиний розклад на прості множники.

Основна теорема арифметики

Кожне ціле число більше 1 можна єдиним чином подати як добуток простих чисел, з точністю до порядку множників. Це одна з найважливіших теорем теорії чисел.

Формати розкладу

Форма добутку: 2 × 2 × 3 × 5

Степенева форма: 2² × 3 × 5

Індексна форма: 2² · 3¹ · 5¹

Приклади

Приклад 1: 12

• 12 = 2 × 2 × 3
• 12 = 2² × 3
• Прості множники: 2, 3

Приклад 2: 60

• 60 = 2 × 2 × 3 × 5
• 60 = 2² × 3 × 5
• Прості множники: 2, 3, 5

Приклад 3: 100

• 100 = 2 × 2 × 5 × 5
• 100 = 2² × 5²
• Прості множники: 2, 5

Методи факторизації

1. Пробне ділення:

• Діліть на найменші прості числа (2, 3, 5, 7...)
• Продовжуйте, доки частка не стане 1
• Просто, але може бути повільно для великих чисел

2. Дерево множників:

• Розбийте число на будь-які два множники
• Продовжуйте, доки всі множники не стануть простими
• Наочно та легко зрозуміти

3. Ділення на прості числа:

• Діліть лише на прості числа
• Ефективніше, ніж пробувати всі числа
• Стандартний алгоритм для комп’ютерів

Крок за кроком: розклад 60

60 ÷ 2 = 30   (2 — просте)
30 ÷ 2 = 15   (2 — просте)
15 ÷ 3 = 5    (3 — просте)
5 ÷ 5 = 1     (5 — просте)

Результат: 60 = 2 × 2 × 3 × 5 = 2² × 3 × 5
            

Знаходження всіх дільників

Після розкладу на прості множники можна знайти всі дільники:

Приклад: 60 = 2² × 3¹ × 5¹

• Для кожного простого множника обирайте степінь від 0 до максимальної
• 2⁰ або 2¹ або 2² → (1, 2, 4)
• 3⁰ або 3¹ → (1, 3)
• 5⁰ або 5¹ → (1, 5)
• Комбінуйте всі варіанти
• Дільники: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Формула кількості дільників

Якщо n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ

Кількість дільників = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)

Приклад: 60 = 2² × 3¹ × 5¹

• Кількість дільників = (2+1) × (1+1) × (1+1)
• = 3 × 2 × 2 = 12 дільників

Формула суми дільників

Сума = [(p₁^(a₁+1) - 1)/(p₁ - 1)] × [(p₂^(a₂+1) - 1)/(p₂ - 1)] × ...

Приклад: 60 = 2² × 3 × 5

• Сума = [(2³-1)/(2-1)] × [(3²-1)/(3-1)] × [(5²-1)/(5-1)]
• = [7/1] × [8/2] × [24/4]
• = 7 × 4 × 6 = 168

Застосування розкладу на прості множники

• Криптографія: RSA шифрування базується на складності факторизації великих чисел
• НСД/НСК: знаходження найбільшого спільного дільника та найменшого спільного кратного
• Спрощення дробів: скорочення до найпростішого вигляду
• Теорія чисел: вивчення властивостей цілих чисел
• Інформатика: хеш-функції, алгоритми

Особливі типи чисел

Досконалі числа:

• Дорівнюють сумі своїх власних дільників
• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14

Надлишкові числа:

• Сума власних дільників > числа
• 12: сума дільників = 1+2+3+4+6 = 16 > 12

Недостатні числа:

• Сума власних дільників < числа
• 8: сума дільників = 1+2+4 = 7 < 8

Степені двійки

Числа — степені двійки мають простий розклад:

• 16 = 2⁴
• 64 = 2⁶
• 256 = 2⁸
• 1024 = 2¹⁰

Високоскладені числа

Числа, що мають більше дільників, ніж будь-яке менше додатне ціле:

• 1 (1 дільник)
• 2 (2 дільники)
• 4 (3 дільники)
• 6 (4 дільники)
• 12 (6 дільників)
• 24 (8 дільників)
• 36 (9 дільників)
• 60 (12 дільників)

Складність факторизації

• Малі числа: легко розкласти вручну
• Великі прості: дуже важко розкласти
• Напівпрості: добуток двох простих, основа RSA
• 200+ цифр: наразі практично нерозв’язно для класичних комп’ютерів
• Квантові комп’ютери: алгоритм Шора може ефективно факторизувати

Поширені розклади

• 10 = 2 × 5
• 12 = 2² × 3
• 15 = 3 × 5
• 24 = 2³ × 3
• 30 = 2 × 3 × 5
• 36 = 2² × 3²
• 48 = 2⁴ × 3
• 100 = 2² × 5²
• 144 = 2⁴ × 3²
• 360 = 2³ × 3² × 5

💡 Порада профі: Щоб швидко перевірити подільність на малі прості числа, пам’ятайте: ділиться на 2, якщо остання цифра парна; на 3, якщо сума цифр ділиться на 3; на 5, якщо остання цифра 0 або 5; на 9, якщо сума цифр ділиться на 9; на 11, якщо почергова сума цифр ділиться на 11. Наприклад, 4356: сума = 4+3+5+6 = 18 (ділиться на 9), отже 4356 ділиться на 9! Починайте факторизацію з цих швидких перевірок перед більшими простими.