我确定一个数字是否为素数的原始函数是：
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))？
