PAT c/c++如何求一个数的所有因子个数，以及所有因子的总和。

Vanessa ·

更新时间:2024-11-13

· 512 次阅读

解题思路：

如果要求一个正整数 N 的因子个数，只需要对其质因子分解，得到各质因子p的个数分别为：
e1、 e2、…、 ek。
于是 N 的因子个数就是：
(e1 + 1) * (e2 + 1) · · · (ek+ 1)。
原因是，对每个质因子 p都可以选择其出现：
0 次、 1 次、．．．、 ei 次，共 ei + 1 种可能
组合起来就是答案。
而由同样的原理可知， N 的所有因子之和为：
（1+p1+p1 ^ 2+…+p1 ^ e1） (1+p2+p2 ^ 2+…p2 ^ e2) … (1+pk+pk ^ 2+…+pk ^ ek) =（1-p1 ^ (e1+1) / (1-p1)）（1-p2 ^ (e2+1) / (1-p2)）*…（1-pk ^ (ek+1) / (1-pk)）。

代码解析如下：

#include
using namespace std;
const int maxn=100010;
int prime[maxn],pnum=0;
bool isprime(int n) {//素数判断打标 
	int sqr=(int)sqrt(1.0*n);
	if(n==1) return false;
	for(int i=2; i<=sqr; i++) {
		if(n%i==0) return false;
	}
	return true;
}
void findprime() {//筛选素数 
	for(int i=1; i<maxn; i++) {
		if(isprime(i)==true) prime[pnum++]=i;
	}
}
int multi(int p ,int e) {//进行指数相乘 
	int nult=1;
	for(int i=0; i>n;
	if(n==1) cout<<"1"<<endl;//特判 
	else {
		int sqr=(int)sqrt(n*1.0);
		for(int i=0; i<pnum&&prime[i]<=sqr; i++) {
			if(n%prime[i]==0) {//如果prime[i]是n的因子 
				fac[num].x=prime[i];//记录该因子 
				fac[num].cnt=0;
				while(n%prime[i]==0) {//计算因子的prime[i]的个数 
					fac[num].cnt++;
					n/=prime[i];
				}
				num++;//不同质因子个数加1 
			}
			if(n==1) break;
		}
		if(n!=1) {//如果无法被根号n以内的质因子除尽 
			fac[num].x=n;//那么一定有一个大于根号n的质因子 
			fac[num++].cnt=1;
		}
		int count=1,sum=1;//调用思路中的公式 
		cout<<"因子总个数："<<endl;
		for(int i=0; i<num; i++) count*=(fac[i].cnt+1);
		cout<<count<<endl;
		cout<<"所有因子总和："<<endl;
		for(int i=0; i<num; i++) {
            sum*=((1-multi(fac[i].x,fac[i].cnt))/(1-fac[i].x));   
		}
		cout<<sum<<endl;
	}
	return 0;
}