c++ - 以下函数的时间复杂度是多少？

Question

#include <iostream>

using namespace std;

bool isPrime(int n){
     if(n == 1 || n == -1)
          return false
     else if (n ==2 || n == 3)
          return true;
     else if((n+1)%6 == 0 || (n-1)%6 == 0)
          return true;
     return false;
}

int main()
{
    int n{0};
    cin >> n;
    cout << isPrime(n) << endl;
    return 0;
}

isPrime() 函数的时间复杂度是多少，检查数字是否为素数是正确的解决方案吗？

标签： c++c++17primes

Answer 1

它只进行少量可分性检查，没有循环或递归，因此它只是O (1) 并且不是正确的素数检查。

第三次检查意义不大。如果一个数与 6 的倍数相差 1，为什么它会是素数？我的意思是它恰好适用于 5 和 7，适用于 11 和 13，以及适用于 17 和 19，但适用于 25。25 与 24 相差一个，但不是素数。这就像将 π 计算为 22/7 一样——这是一个不错的第一个近似值，但它显然不是正确的公式。