约数和素数

约数和素数

一般的约数都是和素数有关系的,在这里将两者放在一起

最基本的求约数方法

(1)试除法求约数   时间复杂度O(√￣n)

下来关于素数  一般采用线性筛素数来快速的初始化所有的素数,时间复杂度O(n)

 (3)约数的个数

如果约数的个数较大,那么一般考虑到约数的倍数,这样可以大大减少复杂度,

相关题目参考1291. 轻拍牛头 - AcWing题库

一般来说一个数N都能表示为:N=p1^s1*p2^s2*p3^3...

这时候该数的约数的个数sum=(s1+1)*(s2+1)*(s3+1)...

那么怎么来将一个数的指数p和系数s记录下来呢?

一般来说要暴力枚举一个数的所有约数是O(√￣n)的

如:

如果这样时间复杂度还比较高的话

可以考虑先找到将这个数变为:N=p1^s1*p2^s2*p3^3...这种形式

然后dfs跑一下,p1的0次幂,1次幂....这样就可以求出来所有的约数了

在int  2e9范围内这样的话 大概只有1600个约数 时间复杂度是很低很低的.

相关题目参考200. Hankson的趣味题 - AcWing题库

另外,要注意  一般int 范围内 若转换为N=p1^s1*p2^s2*p3^3...这种形式

p的个数一般不超过9个 一般将数组的大小定为10即可