#include <stdio.h> #include <string.h>
// 素数判定。注意：n不能太大 int is_prime(int n) { int i; for( i = 2;i*i <= n;i++) if(n % i == 0) return 0; return 1; } // 素数表 int prime[100], count = 0; int main() { // n和各个素数的指数
int i, n,p[100];
// 构造素数表 for( i = 2;i <= 100;i++) if(is_prime(i)) prime[count++] = i; // 把100以内的素数放在 prime数组里 while(scanf("%d",&n) == 1) { printf("%d !=",n); memset(p,0,sizeof(p)); 初始化 数组P int maxp = 0,j; for( i=1;i<=n;i++) {// 必须把i复制到变量m中，而不要在做除法时直接修改它
int m =i; for(j = 0;j < count;j++) while(m%prime[j] == 0) { m/=prime[j]; p[j]++; if(j > maxp) maxp = j; // 更新最大素因子下标 } } // 只循环到最大下标 for(i = 0;i <= maxp;i++) printf("%d",p[i]); printf(" "); } return 0 ; }
一个求素数的函数
int is_prime(int n)
{ int i;
for( i = 2;i*i <= n;i++)
if(n % i == 0) return 0;
return 1;
} 这一部分应该记住。之前有碰见过。（ 一个数n 如果是合数，那么它的所有的因子不超过sqrt（n）-n 的开方）
注意：
做这一题是，不知道如何处理这个N!，如果可以转化成整数，那可以用以前的知识解决了。但是
N很大的时候，就不行了。
理论依据：
也可以写成
num=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]为取整
求N!有几个要注意的地方。
1.最大的质因子不会超过N，
2.关于公式的转化：
式子中把一些东西看成一个整体。举例：
num=N/pi^1+N/pi^2+N/pi^3;
==>
N/p1^1+(N/p1^1)/p1^1+((N/p1^1)/p1^1)/p1^1;
这样的话就可以写成一个solve函数。