问题链接：

问题描述：参见上文。

问题分析：

这是一个整数因子分解问题。

前一个解法是使用计算欧拉函数的基本思想进行分解，即从小因子开始逐步分解。

这个解法则使用Eratosthenes筛选法计算必要的素数放在数组中备用。然后使用这些素数，从小因子开始逐步分解整数。由于素数事先被计算出来，只计算一次，可以重复使用，运行速度相对比较快。

程序说明：（略）。

AC的程序如下：

#include 
    
     #include 
     
      // 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 65535int p[MAXN+1];int main(void){    sieveofe(p, MAXN);    int n;    while(scanf("%d", &n) != EOF) {        divide(p, n);    }    return 0;}