Нахождения простого числа C++

Question

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

int n;

for (i = 2; i < sqrt(n) + 1; ++i) {
    if (n % i == 0) {
    return false;
    }
}
return true;

Answer 1

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

Answer 2

Я бы добавил, что этот код очень легко ускорить в 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) {

БЛОГ НА HUSL

Нахождения простого числа C++

Ответы (2 шт):