[решено] Определение простоты

[fgevat]

Как быстро проверить шести и более значные числа на предмет простоты?

[greg zakharov]

Позвольте полюбопытствовать, это академический интерес или реализуется некий альтернативный криптографический алгоритм? Как бы ни было, позвольте заметить, тема простых чисел отнюдь не так проста. Простите за каламбур. Есть множество различных тестов числа на простоту: от классического "решета" Эратосфена (а также прочие "решето" вроде Сундарама или Аткина) до тестов Соловея - Штрассена и иже с ними. Первый из упомянутых практически не используется, хотя на его основе в той или иной форме плодятся прочие "решето"; большее распространения получил вероятностный алгоритм Миллера - Рабина (например, он используется в Julia (https://julialang.org) модуле 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
)
)
}
}

[DJ Mogarych]

https://www.google.com/search?q=prime+numbers+check+powershell

[fgevat]

DJ Mogarych, вопрос был поставлен не "как мне найти в Google", а вполне определенно. Спасибо товарищу выше за разъяснения (теперь знаю в чем нужно восполнить недостаток знаний). А вас бы я заминусовал была б такая фича на форуме.