检查是否为素数大

Question

我确定一个数字是否为素数的原始函数是:

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))吗？

Answer 1

是的,但这里没有n.新函数的复杂性为O(sqrt(x)).当你说O(N)并且没有指定N是什么时,它通常被认为是输入的大小.这对于采用单个数字参数的函数来说是令人困惑的,因此在这些情况下,您应该是明确的.