Question

指出下列算法（C++函数）的功能并计算出其时间复杂度

int P(int n){
int k=2;
int x=(int)sqrt(n);
while (k<=x){
if(n%k==0) break;
k++;
)
if(k>x) return 1;
else return 0;
}

Answer 1

这个程序的这一句怎么解释：
if(n%k==0) break;

如果 n%k==0，直接退出这次循环，
while循环是在找最小的约数，例如：
n=16，x=4，k从2开始，则第一次while判断时，n%k==0，这就直接返回0了，
所以，返回1是，时间复杂读是x次，返回0时，这个就不好说了，你可以用81，或者其他数字试试

追问

这个函数应该是判断n是否为素数

Answer 2

功能：判断是不是质数，while循环是在找约数
时间复杂度：根号n（应该是..）