一、质数
基础:
1、试除法判定质数
时间复杂度:O(sqrt(n))
2、分解质因数 O(logn ~ sqrt(n))
特别的:数量多数值小的情况:可以考虑先筛质数再根据质数分解质因数(时间复杂度要小10倍左右)
3、筛质数
1)朴素筛O(nlogn)
2)埃筛O(nlognlogn)
3)线性筛O(n)
拓展:线性筛可以同时筛:
Ⅰ、欧拉函数
Ⅱ、莫比乌斯函数
二、约数
基础:
1、试除法求约数
时间复杂度:O(sqrt(n))
2、870. 约数个数
时间复杂度:O(nsqrt(ai))