Калькулятор простых чисел

Простое число (prime number) — это натуральное число больше 1, у которого делителями являются только 1 и оно само. Числа ровно с двумя делителями, такие как 2, 3, 5, 7, 11 и 13, являются простыми, тогда как 4, 6, 8 и 9, имеющие три и более делителей, относятся к составным числам.

Простые числа подобны 'атомам умножения', из которых построено любое натуральное число. Согласно основной теореме арифметики, каждое натуральное число больше 1 единственным образом раскладывается в произведение простых чисел.

Почему это важно

• Криптография: безопасность шифрования с открытым ключом RSA основана на сложности обратного разложения произведения двух больших простых чисел на множители.
• Сокращение дробей: зная простые множители числителя и знаменателя, дробь легко привести к несократимому виду.
• Теория чисел: простых чисел бесконечно много (доказательство Евклида), но их распределение по-прежнему остаётся одной из великих нерешённых задач.

Этот проверщик применяет пробное деление (trial division) с оптимизацией 6k±1. Если n составное, то один из его делителей обязательно не превосходит √n, поэтому, сначала отсеяв 2 и 3, он проверяет только i и i+2, начиная с 5, пока i*i ≤ n.

Ключевые условия: n < 2 → не простое, и если n % i === 0 хоть раз оказывается истинным, число составное.

Например, поскольку √97 ≈ 9,85, число 97 достаточно поделить на 2, 3, 5 и 7. Ни на одно из них оно не делится нацело, поэтому 97 — простое. Напротив, 91 даёт 91 ÷ 7 = 13, то есть 91 = 7 × 13 — составное.

Разложение на простые множители выполняется последовательным делением на наименьшие простые числа, при этом одинаковые множители записываются в виде степеней. Пример: 360 = 2³ × 3² × 5.