Подскажите, простенький тест числа на простоту, пожалуйста. Лучше со ссылками и примерами. Генерируется большое число и надо его проверить является ли оно простым.

П.С. Вообще-то мне задали полиномиальный тест (он же тест АКС - Агравала-Каяла-Саксены), но он какой-то сложный и будет очень медленным, т.к. число хранится в строке. Да и литературы по нему понятной я не нашел.

П.П.С. Под простым я понимаю не "краткость", а простые мат. операции над числом, т.к. число хранится в строке, где 1 символ = 1 цифра. Поэтому собственно тест АКС и не могу реализовать, т.к. там большие степени, извлечение корней и логарифмы.

задан 19 Дек '11 23:00

10|600 символов нужно символов осталось
1

Алгоритм AKS хорошо описан тут. Что значит, число хранится в строке? Логарифм там надо вычислить один раз, так что проблем для вычислений не возникает, причем логарифм такой маленький, что его можно вычислять методом "увеличивать i, пока 2^i<n".

ссылка

отвечен 19 Дек '11 23:50

Мне надо не вручную проверять, а программно. Представьте, что вы не знаете числа целиком, а знаете только его цифры в таком же порядке. Например, число 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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×76

задан
19 Дек '11 23:00

показан
2217 раз

обновлен
20 Дек '11 10:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru