**链接：****传送门 **
题意：给出一个整数 n ，输出整数 n 的分解成若干个素因子的方案
思路：经典的整数分解题目，这里采用试除法 和 用筛法改造后的试除法 对正整数 n 进行分解
方法一：试除法对正整数 n 进行分解
/*************************************************************************
> File Name: hdu1164.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月23日 星期二 22时40分34秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
vector<int> fac[65536];
void init(){
for(int x = 1 ; x <= 65535 ; x++){
int tmp = x , cnt = 0;
for(int i = 2 ; i*i <= tmp ; i++){
while ( tmp % i == 0 ){
fac[x].push_back(i);
tmp /= i;
}
}
if( tmp != 1 ) fac[x].push_back(tmp);
}
}
int main(){
init();
int n;
while(~scanf("%d",&n)){
int len = fac[n].size();
for(int i = 0 ; i < len - 1 ; i++)
printf("%d*",fac[n][i]);
printf("%d\n",fac[n][len-1]);
}
return 0;
}
方法二：筛法对试除法进行优化
原理：相较以试除法不经挑选跑遍整个 [ 1 , sqrt(n) ] ，其中 i = 合数的时候实际上是无效的操作，不如直接打出素数表，跑一下素数表来避免判断大量的合数情况来加速
/*************************************************************************
> File Name: hdu1164t2.cpp
> Author: WArobot
> Blog: http://www.cnblogs.com/WArobot/
> Created Time: 2017年05月23日 星期二 23时06分28秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 65535 + 10;
vector<int> fac[MAX_N];
int prime[MAX_N] = {0} , pri_list[MAX_N] , pri_cnt = 0;
void init_prime(){
for(int i = 2 ; i*i < MAX_N ; i++){
if( prime[i] == 0 ){
pri_list[ pri_cnt++ ] = i;
for(int j = 2*i ; j < MAX_N ; j += i) prime[i] = 1;
}
}
}
void init_ans_list(){
for(int x = 1 ; x < MAX_N ; x++){
int tmp = x , cnt = 0;
for(int i = 0 ; pri_list[i] <= tmp && i < pri_cnt ; i++){
while( tmp % pri_list[i] == 0 ){
fac[x].push_back(pri_list[i]);
tmp /= pri_list[i];
}
}
if( tmp != 1 ) fac[x].push_back(tmp);
}
}
int main(){
init_prime();
init_ans_list();
int n;
while(~scanf("%d",&n)){
int len = fac[n].size();
for(int i = 0 ; i < len-1 ; i++) printf("%d*",fac[n][i]);
printf("%d\n",fac[n][len-1]);
}
return 0;
}