• 欢迎光临~

AcWing 算法提高课 筛质数

开发技术 开发技术 2022-10-01 次浏览

例题:

1、求区间中的质数

筛质数是O(n)或O(nloglogn)

但是如果n很大,则会超时。

 

但是如果要筛[l, r]区间中的全部质数

且l和r比较大,但是r-l比较小时。

可以用O(nloglogn)的时间筛出,其中n=sqrt(N)。可以降低时间复杂度。

 

有对一个数n,如果是合数,则一定有小于sqrt(n)的一个质因子。

利用埃氏筛法的思想:

可以先预处理出sqrt(N)内的全部质数,再用这些质数去筛[l, r]之间的数。

注意不要把质数本身筛掉,且注意处理1

例题:https://www.acwing.com/problem/content/submission/198/

 

2、求一个阶乘的分解质因子结果

由于阶乘很大,直接分解质因子不行。

但是如果阶乘运算n!的n比较小的话。

可以考虑先筛出1-n中全部的质数,

然后用全部质数p去算1-n中的p的倍数,其中有多少p因子

注意,由于可能会有多个p因子,可以考虑用p、p^2、p^3...筛多次,或者可以在用p筛的时候,直接用除法统计有几个p因子

并累加(因为阶乘会把1-n全部数乘起来,故其质因子分解的结果可以视为将每个数的分解质因子结果相加)。

例题:https://www.acwing.com/problem/content/199/

程序员灯塔
转载请注明原文链接:AcWing 算法提高课 筛质数
喜欢 (0)