博客

#include<iostream>
using namespace std;
/*
	实现100!有多少个约数 
*/
int n;
int dp[100];
int p[100];
int a[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
long long ans=1;
bool flag;
void dfs(int x,int mul,int num){
	if(flag){
		return;
	}
	if(x<mul){
		return;
	}
	if(x==mul){
		flag=true;
		cout<<x<<":";
		for(int j=0;j<n;j++){
			if(p[j]){
			cout<<p[j]<<"*";
			dp[p[j]]++;	
			}
		}
		cout<<endl;
		return;
	}
	for(int i=0;i<25;i++){
		if(!flag&&a[i]*mul<=x&&x%a[i]==0){
			p[num]=a[i];
			//cout<<num<<","<<p[num]<<endl;
			dfs(x,mul*a[i],num+1);	
		}else if(a[i]*mul>x){
			p[num]=0;
			return;
		}
	}
} 
int main(){
	cout<<"请输入100以内的数："<<endl; 
	cin>>n;
	for(int i=2;i<=n;i++){
		for(int k=0;k<n;k++){
			p[k]=0;
		}
		flag=false;
		dfs(i,1,0);
	}
	for(int i=2;i<=n;i++){
		if(dp[i]){
			ans=ans*(dp[i]+1);
		}
	}
	cout<<ans<<endl;
	return 0;
} 

不知道正确答案是多少哈
这个代码算出来是39001250856960000

主要思路是100!=100*99*97*....*1
根据 信息安全数学基础 课本的结论
任何一个数都可以表示为奇素数的乘积
所以这里采用dfs，将每个数表示为奇素数的乘积
同时统计每个奇素数出现的次数
我们需要的是每个奇素数出现的总次数
因为如下定理
若正整数n可分解为p1^a1*p1^a2*...*pk^ak
其中pi为两两不同的素数,ai为对应指数，则n的约数个数为(1+a1)*(1+a2)*....*(1+ak)
例如
180=2*2*3*3*5=2^2*3^2*5
180的约数个数为(1+2)*(1+2)*(1+1)=18个。
当然本例子摘抄自网络

答案如果有问题，提醒我修改哈！