因子和阶乘
时间限制：
1000 ms | 内存限制：
65535 KB
难度：
2
- 描述
-
给你一个正整数n，把n!=1x2x3x.....xn分解成素因子相乘的形式，并从小到大输出每个素因子的指数，但要保证最后输出的素因子个数不为0。例如825应表示为0,1,2,0,1表示分别有0,1,2,0,1个2,3,5,7,11。
- 输入
-
第一行有一个整数n(0<n<10000),表示有n组测试数据；
接下来n行每行有一个整数 m(1<m<10000) - 输出
- 从小到大输出m分解成素因子相乘后各个素因子对应的指数
- 样例输入
-
2 5 53
- 样例输出
-
3 1 1 49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1
#include<stdio.h> #include<math.h> #include<string.h> #define N 10005 bool visit[N]={1,1,0}; int b[2000];//素数定理 ,N/lnN void Prime() { int i,j,k=0; int m=(int)(sqrt(N)+0.5); for(i=2;i<m;i++) if(!visit[i]) for(j=i*i;j<N;j+=i) visit[j]=1; for(i=2;i<N;i++) if(!visit[i]) b[k++]=i;//实际上直接在第二层for之上加上b[k++]=i即可 } int cnt(int n,int m)//n！含几个m { int ans=0; while(n>0) { n=n/m; ans+=n; } return ans; } int main() { int i,j,k,m,n; Prime(); scanf("%d",&n); while(n--) { scanf("%d",&m); for(i=0;b[i]<=m;i++)/*有 b[i]<=m实际上已经限制了不会输出素数指数为0的 指数 */ printf("%d ",cnt(m,b[i]));//另外最后的i表示m含有几个不同的素因子 putchar('\n'); } }
或者
/*不同质因子个数
while(n)
{
if(n%prim[i]==0)
{
cnt++;
while(n%prim[i]==0)
n/=prim[i];
}
i++;
}
/* 求a！因式中有多少个b（b是素数） 那么a / b 表示 在 1 到 a 中所有的数中有a/b个能够整除b a / (b^2) 表示在 1 到 a 中所有的数中有a/(b^2)个能够整除b^2 …… 因此，总共有a/b + a / b^2 + a / b^3 + …… 直到a/ b^n 等于0 注释：2是足够的关键看有几个5，以100为例，先除以5，除尽的有5,10，15,20，……100等20个数， 得到1,2……20；再除以5，除尽的有5,10,15,20这4个数；于是共24个5，即24个0。因此看出来求n!含有几个x，实际是看1到n各个数各有几个x；最后再相加 于是但求某个数n含有几个x ，比如12含有2个2；先12%2=0,则有一个2；12/2=6, 6%2=0，则有两个2了；6/2=3,3%2=1!=0;则总共2个2 */
