[решено] Определение простоты - Компьютерный форум OSzone.net

Позвольте полюбопытствовать, это академический интерес или реализуется некий альтернативный криптографический алгоритм? Как бы ни было, позвольте заметить, тема простых чисел отнюдь не так проста. Простите за каламбур. Есть множество различных тестов числа на простоту: от классического "решета" Эратосфена (а также прочие "решето" вроде Сундарама или Аткина) до тестов Соловея - Штрассена и иже с ними. Первый из упомянутых практически не используется, хотя на его основе в той или иной форме плодятся прочие "решето"; большее распространения получил вероятностный алгоритм Миллера - Рабина (например, он используется в Julia модуле Primes и показывает хорошие результаты теста числа на простоту), его не так уж и сложно реализовать в pwsh.
А вообще, если пораскинуть мозгами, то:
- число кратное двум и пяти, то есть числа ≥ 10 и оканчивающиеся на 0, 2, 4, 6, 8 и 5, не могут быть простыми по определению
- если квадратный корень тестируемого числа является натуральным числом, тестируемое число не является простым
- целая часть рационального числа, являющегося результатом извлечения квадратного корня из тестируемого числа, является пределом поиска делителя
- потенциальные простые числа оканчиваются на 1, 3, 7 и 9, то есть нечётные числа, следовательно, поиск делителя осуществляется по нечётным числам
- вероятностный алгоритм в купе с изложенным выше снижает затраты на определение простоты
Вариант "на коленке" (без использования вероятностных алгоритмов):

Код:

function Test-Prime {

  [CmdletBinding()]

  param(

    [Parameter(Mandatory)]

    [ValidateRange(2, [UInt64]::MaxValue)]

    [UInt64]$Number

  )



  end {

    $Number -in (2, 5) ? $true : $(

      ($x = [Math]::Sqrt($Number)) -eq [Math]::Floor($x) ? $false : $(

        ($Number % 10) -in (1, 3, 7, 9) ? $(

          for ($i = 3; $i -lt $x; $i += 2) {

            if (($Number % $i) -eq 0) {

              Write-Verbose "Возможный делитель $i"

              return $false

            }

          }

          $true

        ) : $false

      )

    )

  }

}