题目
Description
给出一个正整数m, 将其分解成质数相乘的形式,即 m=m1m2m3*....*mk. 其中mi为质数,并且满足m1<=m2<=m3<=....<=mk。若m本身就是质数,则直接输出m=m即可。
Input
输入包括多组测试数据,每组测试数据占一行,并且只有一个正整数m,当m=0时,表示输入结束。
Output
对每组测试数据输出一个结果,并占一行。
Sample Input
12
5
2310
0Sample Output
12=2*2*3
5=5
2310=2*3*5*7*11
题解
第一步首先是要得到一个质数表
使用 >筛法求质数<
得到质数表后,从小到大试除每一个质数(可以相等)
每有一个满足就输出这个数即可
代码
/* By:OhYee Github:OhYee Blog:http://www.oyohyee.com/ Email:oyohyee@oyohyee.com かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <functional> using namespace std; const int maxn = 1000005; int prime[maxn] = {0},num_prime = 0; bool isNotPrime[maxn] = {1,1}; void Prime() { for(long i = 2;i < maxn;i++) { if(!isNotPrime[i])prime[num_prime++] = i; for(int j = 0;j < num_prime&&i*prime[j] < maxn;j++) { isNotPrime[i*prime[j]] = true; if(!(i%prime[j]))break; } } } bool Do() { int n; scanf("%d",&n); if(n == 0) return false; printf("%d=",n); if((n < maxn) && (!isNotPrime[n] || n == 1)) { printf("%d\n",n); } else { bool first = true; for(int i = 0;i < num_prime && n>1;i++) { while(!(n%prime[i])) { if(!first) printf("*"); first = false; printf("%d",prime[i]); n /= prime[i]; } } printf("\n"); } return true; } int main() { Prime(); while(Do()); return 0; }