http://acm.hdu.edu.cn/showproblem.php?pid=1164
问题分析：
这是一个整数因子分解问题。有两种解法，一是按照欧拉函数计算的思想实现，二是采用筛选法。
方法一：采用计算欧拉函数的基本思想进行分解，即从小因子开始逐步分解。
这周方法需要注意的是，对于需要分解的整数n，最后被分解到只剩下1时，不需要输出，即不输出1。
方法二：使用Eratosthenes筛选法计算必要的素数放在数组中备用。然后使用这些素数，从小因子开始逐步分解整数。由于素数事先被计算出来，只计算一次，可以重复使用，运行速度相对比较快。
#include <stdio.h> #include <math.h> // Eratosthenes筛选法 void sieveofe(int p[], int n) { int i, j; p[0] = 0; p[1] = 0; p[2] = 1; // 初始化 for(i=3; i<=n; i++) { p[i++] = 1; p[i] = 0; } int max = sqrt(n); for(i=3; i<=max; i++){ if(p[i]) { for(j=i+i; j < n; j+=i) //进行筛选 p[j]=0; } } // 整理数组p，将素数放在前面的单元中 p[0] = 2; j = 1; for(i=3; i<=n; i++) if(p[i]) p[j++] = i; } // 利用计算得到的素数（数组p中），进行分解（超时） void divide(int p[], int n) { int count = 0, i = 0; while(n > 1) { while(n % p[i] == 0) { n /= p[i]; if(++count == 1) printf("%d", p[i]); else printf("*%d", p[i]); } i++; } printf("\n"); } #define MAXN 65535 int p[MAXN+1]; int main(void) { sieveofe(p, MAXN); int n; while(scanf("%d", &n) != EOF) { divide(p, n); } return 0; }
或者：
#include <stdio.h> #include <math.h> // 欧拉函数法 void divide(int n) { int count = 0, i; while(n%2 == 0) { n /= 2; if(++count == 1) printf("2"); else printf("*2"); } for(i=3; i*i<=n; i+=2) { if(n%i == 0) { n /= i; if(++count == 1) printf("%d", i); else printf("*%d", i); while(n%i == 0) { n /= i; printf("*%d", i); } } } if(n != 1) { if(++count == 1) printf("%d", n); else printf("*%d", n); } printf("\n"); } int main(void) { int n; while(scanf("%d", &n) != EOF) divide(n); return 0; }
