以下关于素数判定算法的描述中，正确的是？

kc829417 单选题共个子题

素数是指大于1且除了1和自身外无其他正因数的自然数。

最朴素的素数判定算法需要遍历从2到n-1的所有整数判断是否能整除n，该算法时间复杂度为O(n)，是最优的素数判定算法。

优化后的试除法素数判定算法只需遍历从2到√n的整数即可，时间复杂度降低为O(√n)，是实际应用中常用的基础素数判定方法。

如果一个数n是合数，那么它必然有一个大于√n的因数，因此只需遍历到√n即可完成判定。

素数判定算法无法进行优化，所有实现的时间复杂度都无法低于O(n)。

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析