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

Vanessa ·
更新时间:2024-11-10
· 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; } Nirvana Soar 原创文章 20获赞 23访问量 1087 关注 私信 展开阅读全文
作者:Nirvana Soar



pat c+ C++

需要 登录 后方可回复, 如果你还没有账号请 注册新账号