|
Подскажите, простенький тест числа на простоту, пожалуйста. Лучше со ссылками и примерами. Генерируется большое число и надо его проверить является ли оно простым. П.С. Вообще-то мне задали полиномиальный тест (он же тест АКС - Агравала-Каяла-Саксены), но он какой-то сложный и будет очень медленным, т.к. число хранится в строке. Да и литературы по нему понятной я не нашел. П.П.С. Под простым я понимаю не "краткость", а простые мат. операции над числом, т.к. число хранится в строке, где 1 символ = 1 цифра. Поэтому собственно тест АКС и не могу реализовать, т.к. там большие степени, извлечение корней и логарифмы. задан 19 Дек '11 23:00 
ray |
|
Алгоритм AKS хорошо описан тут. Что значит, число хранится в строке? Логарифм там надо вычислить один раз, так что проблем для вычислений не возникает, причем логарифм такой маленький, что его можно вычислять методом "увеличивать i, пока 2^i<n". отвечен 19 Дек '11 23:50 
freopen Мне надо не вручную проверять, а программно. Представьте, что вы не знаете числа целиком, а знаете только его цифры в таком же порядке. Например, число 6527 в строке-массиве = [6],[5],[2],[7]. И как вычислять логарифм такого числа? Корень-то вроде можно примерно полчисла отбросить и все.
(20 Дек '11 0:08)
ray
1
Я догадался, только проблемы все равно не вижу. Если непонятно, что я написал, вот способ попроще. Там же необязательно точно знать логарифм. Берем количество цифр и умножаем на 4 - ошибемся меньше чем в два раза, для сложности некритично. С такой задачей Вы справитесь?
(20 Дек '11 0:31)
freopen
С корнем вообще проблем нет, он же меньше, чем 16 log^5 n, т.е. не очень большой.
(20 Дек '11 0:33)
freopen
|