质因子

大家好，欢迎来到IT知识分享网。

1.质因子分解

首先明确概念：

质数==素数，质因子分解指将一个正整数n写成一个或多个质数的形式。例如，180=2*2*3*3*5

解决该问题的前提，我们要解决素数的求解，可见下面的博客。

质因子

考虑到每个质因子都可以不止出现一次，也就是我们不仅要知道质因子，还要知道它的个数，这两个都是它的属性，所以采用结构体保存，

struct factor{ int x; int cnt; }

具体算法：

首先我们利用筛选法得到素数表后，只要访问素数表，判断该素数p是否为n的因子；

1.如果是，那么保存该因子，同时让n继续整除p,记录该因子的次数，直到不能除尽为止；

2.如果不是，直接跳过即可。

for(int i=0;prime[i]<=n;i++){ if(n%prime[i]==0){ fac[num].x=prime[i]; fac[nim].cnt=0; while(n%prime[i]==0){ fac[num].cnt++; n/=prime[i]; } num++; //准备保存下一个因子 } }

可以看到，上面循环中，当n很大时，大概率超时；

考虑到对一个正整数n来说，它的质因子要么全部小于等于sqrt(n)，要么只存在一个大于sqrt(n)的数，算法改进。

for(int i=0;prime[i]<=sqrt(n);i++){ if(n%prime[i]==0){ fac[num].x=prime[i]; fac[nim].cnt=0; while(n%prime[i]==0){ fac[num].cnt++; n/=prime[i]; } num++; //准备保存下一个因子 } if(n==1) break; //及时退出循环 } if(n!=1){ //如果无法被sqrt(n)以内的质因子除尽 fac[num].x=n; //那么一定有一个大于sqrt(n)的质因子 fac[num].cnt=1; }

拓展应用

考虑到有数学定理，合数都可写成几个素数的乘积；那么我们可根据求得的质因子获得正整数n的因子个数。假设各质因子pi的个数分别是e1,e2…ek;

于是根据组合因子出现的次数，n的因子个数就是(e1+1)*(e2+2)…..(ek+1);

于是可以得到n的因子数之和，（1+p1+p1^2+…p1^ei)*(1+p2+p2^2+…p2^e2)….;

2.求质因子个数

给定一个整数n，求n！中有多少质因子p；

最简单的想法就是去判断1-n中每个数有多少质因子p，然后结果累积。

int cal(int n ,int p){ int ans=0; for(int i=2;i<=n;i++;){ int temp=i; while(temp%p){ ans++; temp/=p; } } return ans; }

 很明显，当数据很大会超时；

我们可以找到规律；n!中有个质因子p，于是有一下算法O(log n)；

int cal(int n,int p) { int ans=0; while(n){ ans+=n/p; n/=p; //相当于分母多乘一个p } return ans; } 

同时根据情况：n!中质因子的个数实际上等于1-n中p的倍数加上中质因子p的个数，所以有递归写法,

int cal(int n,int p) { if(n<p) return 0; return n/p+cal(n/p,p) }