Введение
Вы абсолютно правы! Тест на простоту — это алгоритм, который определяет, является ли данное натуральное число простым или составным.
В данной статье я хочу рассказать о тесте, который не так распространен, и о котором нет информации на русской Википедии. Название этого теста мне также неизвестно.
Метод гласит, что если число p простое, то из уравнения:
Если каждое ak кратно p, то p — простое число.
В данной статье я хочу протестировать данную гипотезу/теорему на поиске всех простых чисел от 1 до произвольного натурального n>3.
Разберемся с коэффициентами
Коэффициентыak представляют собой ничто иное, как биномиальные коэффициенты. Это несложно понять, воспользовавшись формулой бинома Ньютона:
То есть задача сводится к проверке кратности p всем биномиальным коэффициентам.
Поскольку биномиальные коэффициенты симметричны, нам достаточно проверить только половину из них.
Еще один факт, который позволит проверять меньше чисел, заключается в том, что любое простое число (кроме 2 и 3) можно представить в виде 6n−1 или 6n+1 для любого натурального n.
Пишем код
Первым делом необходимо сгенерировать сами числа от 4 до n>3 и объединить с числами 2 и 3 (их нельзя проверить по правилу 6n).
(BigInt(2) to BigInt(3)).union((4 to StdIn.readInt()) ... )В Scala выражение (a to b) генерирует вектор из всех чисел от a до b.
Затем отфильтруем все числа (кроме 2 и 3) по правилу 6n.
val simples = (BigInt(2) to BigInt(3)).union((4 to StdIn.readInt())
.filter(p => (p - 1) % 6 == 0 || (p + 1) % 6 == 0) //фильтрация по правилу 6n
)Теперь для каждого из оставшихся чисел будем делать проверку на простоту.
.filter(p =>
(2 until (p + 1) / 2)
.scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k)
.map(k => k % p).sum == 0)(2 until (p + 1) / 2) - данная строчка генерирует вектор от 2 до(p+1)/2−1.
Вспомним формулу бинома:
Разделим коэффициент при k на биномиальный коэффициент при k−1.
Данная формула позволит считать коэффициенты в векторе на много быстрее,
и не придется для каждого числа по отдельности считать факториалы.
Заметим также, что:
Давайте вернемся к коду.
.scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k) - scanLeft это то же самое, что и foreach, с той лишь разницей, что позволяет узнать результат предыдущей итерации (left) с пропуском первого значения, инициализируя его в начале как BigInt(p). Затем в (left, k) => left * (p - k + 1) / k уже сами считаем коэффициенты по упрощенной формуле.
.map(k => k % p).sum == 0 - в данном от всех коэффициентов вычисляется модуль по p, и затем считается сумма остатков, что позволяет определить, все ли коэффициенты кратны p.
Теперь весь код целиком выглядит так:
import scala.io.StdIn
object UniversePolinomeTest extends App {
print("введите натуральное число (n) больше 3: ")
val primes = (BigInt(2) to BigInt(3)).union((4 to StdIn.readInt())
.filter(p => (p - 1) % 6 == 0 || (p + 1) % 6 == 0)
.filter(p =>
(2 until (p + 1) / 2)
.scanLeft(BigInt(p))((left, k) => left * (p - k + 1) / k)
.map(k => k % p).sum == 0)
)
println(s"все просты числа до n : $primes")
println(s"найдено простых чисел: ${primes.size}")
}Во всей программе я использую длинную арифметику (BigInt), поскольку Int и Long быстро перестают справляться, так как факториалы слишком быстро растут.
Результат/Заключение
Данный код/метод справляется достаточно точно. Ниже приведен пример для чисел до 10000 (после 19 идет много чисел, которые проблематично уместить в кадре).
Хотя код/метод и справляется с достаточно большим количеством чисел, я не стану утверждать, что он работает на 100% случаев.
