判断题 偏易
#18312

求解指定正整数范围内所有质数,采用线性筛算法比埃氏筛效率更高。( )

求解指定正整数范围内所有质数,采用线性筛算法比埃氏筛效率更高。( )

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析

埃氏筛:算法思想,从小到大枚举每个素数,将其所有的倍数标记为非素数。效率,时间复杂度约为O(n log log n),其中n是给定范围内的最大整数。

线性筛法:算法思想,类似于埃氏筛,但是通过线性的方式来标记非素数,而不是简单地使用倍数关系。效率,时间复杂度为O(n),相对于埃氏筛有更好的性能。