Введение

Вы абсолютно правы! Тест на простоту — это алгоритм, который определяет, является ли данное натуральное число простым или составным.

В данной статье я хочу рассказать о тесте, который не так распространен, и о котором нет информации на русской Википедии. Название этого теста мне также неизвестно.

Метод гласит, что если число p простое, то из уравнения:

{(x-1)}^p-(x^p-1) = \sum_{k=0}^{p} a_kx^k \\a_k - коэфициент\ при\ x^k

Если каждое ak​ кратно p, то p — простое число.

∀{p \in \mathbb{N}} ((D(p) → P(x)) ∧ (¬D(p) → ¬P(x))) \\P(p) - число\ являяется\ простым \\ D(p): (x-1)^p - (x^p-1) = \sum_{k=0}^{p} a_kx^k\ все\ коэффициенты\, кратные\ p.

В данной статье я хочу протестировать данную гипотезу/теорему на поиске всех простых чисел от 1 до произвольного натурального n>3.

Разберемся с коэффициентами

Коэффициентыak представляют собой ничто иное, как биномиальные коэффициенты. Это несложно понять, воспользовавшись формулой бинома Ньютона:

{(x-1)}^p-(x^p-1) = \sum_{k=0}^{p} (-1)^{p - k}C_p^kx^k -(x^p -1 ) = \sum_{k=1}^{p - 1} (-1)^{p - k} C_p^kx^k

То есть задача сводится к проверке кратности p всем биномиальным коэффициентам.

C_p^k \ ⋮ \ \ p, k = \overline{1,k - 1}

Поскольку биномиальные коэффициенты симметричны, нам достаточно проверить только половину из них.

C_p^k \ ⋮ \ \ p, k = \overline{1,(p +1)/ 2 }

Еще один факт, который позволит проверять меньше чисел, заключается в том, что любое простое число (кроме 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.

Вспомним формулу бинома:

C_p^k = \frac{p!}{k!(p - k)!}

Разделим коэффициент при k на биномиальный коэффициент при k−1.

\frac{C_p^{k}}{C_p^{k - 1}} = \frac{p!}{(k)!(p - k)!}/ \frac{p!}{(k - 1)!(p - k + 1)!} = \frac{p-k + 1}{k}

Данная формула позволит считать коэффициенты в векторе на много быстрее,
и не придется для каждого числа по отдельности считать факториалы.

Заметим также, что:

С_p^1 = p

Давайте вернемся к коду.

.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% случаев.

P.S.

Код можно посмотреть на GitHub