Question

数据结构 时间复杂度

阅读下面程序，指出其算法的功能并求出其时间复杂度。
int Prime(int n){
int i=2,x=(int)sqrt(n);
while(i<=x){
if(n%i==0)break;
i++;
}
if(i>x) return 1;
else return 0;
}

Answer 1

Answer 2

o（N的二份一次方）

Answer 3

该函数的功能是：判断一个整数是否为素数，是素数返回1，不是素数返回0
算法流程：
参数为整数n
对n开平的方并取整后赋值给整型变量x
循环判断：令i从2开始递增，一直到i<=x不成立
在循环体中判断n能不能被i整除，一旦有一个i能整除就说明不是素数，就提前跳出循环
最后判断i是否大于x,(如果没有提前跳出循环，则最后i会等于x+1)
如果i>x则n是素数，返回1，否则返回0
【时间复杂度】最大时间复杂度为(根号n)
因为在上面的算法中最多循环x次，即根号n