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

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() 函数的时间复杂度是多少？检查数字是否为素数是否正确？

Answer 1

它只做了少量的可除性检查，没有循环或递归，因此它只是 O(1)，不是正确的素数检查。

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