c – 检查是否为素数大

bool is_prime(int x) {
    for (int y = 2; y < x; ++y) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

这可能是复杂的O(x),因为你可能不得不去x.

我已经了解了一些优化,需要检查我的big-o.这是改进的计划：

bool is_prime(int x)
{   
    if (x % 2  == 0 && x > 2) {
        return false;
    }
    for (int y = 3; y*y <= x; y += 2) {
        if (x % y == 0) {
            return false;
        }
    }
    return true;
}

我现在上升到sqrt()的事实是否将其更改为O(sqrt(x))？