0

Увидел алгоритм нахождения простого числа и не могу понять для чего нужно +1 ( i < sqrt(n) + 1 ), код и без нее нормально работает, или эта единица как-то оптимизирует код? На что она влияет?

int n;

for (i = 2; i < sqrt(n) + 1; ++i) {
    if (n % i == 0) {
    return false;
    }
}
return true;
3
  • 1
    надо же, чтобы цикл выполнился и для значения sqrt(n). а раз там написано «строго меньше», то последняя итерация будет выполнена для числа sqrt(n)-1. можно не добавлять единицу, а убрать строгость из сравнения — заменить его на «меньше или равно». 21 дек 2022 в 12:54
  • 3
    плюс то, что может получиться что-нибудь вроде sqrt(100000000)=9999.99997, и прибавление единицы страхует от таких случаев
    – MBo
    21 дек 2022 в 12:59
  • 1
    Резюмируя два комментария выше: надо <= sqrt(n)+1 :)
    – Harry
    22 дек 2022 в 7:11

2 ответа 2

4

Это сделано для случая, если ваше число - квадрат простого числа. Тогда его первым и единственным нетривиальным делителем будет его корень. А если вы будете проходить циклом до тех пор, пока i < sqrt(n), то вы до него не дойдёте и ваша функция скажет, что это число простое. Попробуйте запустить код без этой + 1 при n = 25.

4

Я бы добавил, что этот код очень легко ускорить в 2 раза...

if (n%2==0) return false;
for (i = 3; i <= sqrt(n) + 1; i+=2) { // См. мой комментарий к вопросу
    if (n % i == 0) {
    return false;
    }
}

Еще условие завершения цикла можно записать как

for (i = 3; i*i <= n; i+=2) {
4
  • Возможно Вы имели в виду второй return true. Но даже так алгоритм работает некорректно и неправильно определяет простые числа.
    – Д--
    22 дек 2022 в 14:57
  • @Д-- ideone.com/mLl7QI — где?
    – Harry
    22 дек 2022 в 17:53
  • i <= sqrt(n) + 1. Зачем <=? Не лучше ли <? 26 дек 2022 в 16:54
  • @StanislavVolodarskiy Можно и так. Главное было в i+=2.
    – Harry
    26 дек 2022 в 18:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.