|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 |
#include <stdio.h>#include <string.h><br>// 素数判定。注意：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和各个素数的指数<br>int i, n,p[100];<br>// 构造素数表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)); 初始化 数组Pint
maxp = 0,j;for( i=1;i<=n;i++){// 必须把i复制到变量m中，而不要在做除法时直接修改它<br> 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("\n");}return
0 ;} |
一个求素数的函数
|
1
2
3
4
5
6 |
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 的开方）<br><br> |
原文：http://www.cnblogs.com/joyclub/p/3618806.html