检查是否为质数大o

Question

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

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

这运行的复杂性O(x)因为您可能不得不去x。

我已经了解了一些优化，需要检查我的大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是什么时，它通常被认为是输入的大小。这对于采用单个数字参数的函数来说是令人困惑的，因此在这些情况下，您应该显式。

Answer 2

当然， 新功能的复杂性是

O(sqrt(x((

但是，仍然有一些优化的空间。看看下面提到的代码：

bool isPrime(int n)
{
// Boundary cases
if (n <= 1)  return false;
if (n <= 3)  return true;
// This is checked so that we can skip 
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}