如果要求一个正整数 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
关注
私信
展开阅读全文