Как мне улучшить сложность этого алгоритма рандомизированного тестирования простоты?
Я написал следующую программу, которая возвращает 1, если число простое, и 0, если оно составное.
Хотя есть возможность ошибочно идентифицировать состав как простое. Я хочу предложения по улучшению (уменьшению) временной сложности для следующего алгоритма.
int compute(int n)
{
int x;
for(int i = 1; i < 100 * sqrt(n); i++)
{
x = rand() % ((int)sqrt(n) + 1);
if(x != 0 && x != 1 && x!=n)
{
if(n % x == 0)
return 0;
}
}
return 1;
}
Решение
Возможно, вы захотите взглянуть на Тест первичности Миллера-Рабина. В этом тесте
Вы используете серию «свидетельских» значений и выполняете некоторые вычисления. Каждый свидетель
расчет дает результат «составной» или «возможно, простое». Если вы используете K свидетелей
и все они дают «возможно простые» результаты, вероятность того, что число на самом деле
составной 1/4 ^ к.
Время выполнения равно O (k log ^ 3 n), что является существенным улучшением по сравнению с вашим O (sqrt (n))
алгоритм.
Другие решения