下面判断n是否为素数的算法，其时间复杂度为多少？急啊！！谢了

下面判断n是否为素数的算法，其时间复杂度为多少？
int PMe(int n)
{
int i=1;
int x=(int) sqrt(n);
while (++i<=x)
if (n%i==0) break;
if (i>x) return 1;
else return 0;
}

举报该问题

其他回答

第1个回答推荐于2017-11-24

int PMe(int n)
{
int i=1;//这个语句花费了常数时间，记为o（1）
int x=(int) sqrt(n);;//这个语句花费了常数时间，记为o（1）
while (++i<=x)
if (n%i==0) break;//这个while 循环最多一共运行x次，所以花费了o（sqrt（n））的运行时间
if (i>x) return 1;
else return 0;);;//这个if...else语句花费了常数时间，记为o（1）
}
所以整个算法花费了o（1）+o（1）+o（sqrt（n））+o（1），所以时间复杂度就是o（sqrt（n））。
至于为什么 o（1）+o（1）+o（sqrt（n））+o（1）=o（sqrt（n）），建议您去看麻省理工学院的公开课《算法导论》的第一大部分：基础。在第三章和第四章，讲的很详细。本回答被提问者采纳

第2个回答 2011-12-31

sqrt（n）

第3个回答 2011-12-30

根号n的时间复杂度

第4个回答 2011-12-30

根号n
sqrt (n)

相似回答

数据结构题答：1 返回的的为（a2,a3,...,an,a1)2 时间复杂度主要看其循环的次，本题的时间复杂度为： O(根号n),（这个字符不好打，就写汉字了），而且最好不用sqrt(n),计算耗时，用 i*i<n，会快一些

判定素数的方法有哪些?它们的时间复杂度分别是多少?(越详细越好,有高分...答：用n除以2-sqrt(n),有一个能除尽就不是素数，否则是素数。时间复杂度：O(sqrt(n))2、素数判断法：这种方法是对上面方法的改进，上面方法是对2-sqrt(n)之间的数进行判断是否能除尽，而因为有如下算术基本定理，可以减少判断量。算术基本定理：又称为素数的唯一分解定理，即：每个大于1的自然数均可...

判断一个正整数N是不是素数的程序在最坏的情况下时间复杂度是多少答：一般判断素数的方法：1）朴素算法，除数逐个尝试，直到出现整除或者到自己本身复杂度0(n)2)筛素数法，把合数全筛选出来，复杂度也是o(n)3)rabin miller算法，利用费马定理和欧拉定理，随机挑选数来试验，复杂度为o(1)

c语言中素数的判定方法答：最常见的素数判定方法是试除法。即对于给定的正整数n，从2开始逐个除以小于n的数，如果存在能整除n的数，则n不是素数;如果不存在能整除n的数，则n是素数。这种方法的时间复杂度为O(n)。2、优化方法为了提高素数判定的效率，可以对试除法进行一些优化。例如，可以只试除小于等于n的平方根的数，因为...

数据结构 时间复杂度视频时间 09:56

素数寻找算法答：探索素数的高效算法：暴力求解、埃氏筛法与欧拉筛的比较在寻找素数的道路上，算法的选择至关重要。暴力求解虽然直观，但其时间复杂度却高达 O(n*sqrt(n))。这种方法的原理是，每个数的因数对与其平方根对称分布，因此只需检查 [2, sqrt(i)] 内是否有因数即可，如以下代码所示：vector<int> findPrim...

如何判断n是否是素数答：方法一：判断n是否能被2~n-1间的整数除方法二：判断n是否能被2~√n间的整数除 C语言中——三种方法判断是偶数还是奇数开头代码：include <stdio.h> int main(int argc, const char * argv[]){int a;printf("请输入一个数:");scanf("%d",&a);方法一：求余 if (a%2) { printf...

大家正在搜

时间复杂度为n的算法时间复杂度为n的排序算法从1加到n的算法的时间复杂度算法时间复杂度n的平方用递归算法求n的阶乘时间复杂度算法的时间复杂度与什么有关 n皇后算法问题时间复杂度 n皇后算法时间复杂度时间复杂度中的n是什么意思

下面判断n是否为素数的算法，其时间复杂度为多少？ 急啊！！谢了

下面判断n是否为素数的算法，其时间复杂度为多少？急啊！！谢了