题目

Description

给出一个正整数m, 将其分解成质数相乘的形式，即 m=m1m2m3*....*mk. 其中mi为质数，并且满足m1<=m2<=m3<=....<=mk。若m本身就是质数，则直接输出m=m即可。

Input

输入包括多组测试数据，每组测试数据占一行，并且只有一个正整数m，当m=0时，表示输入结束。

Output

对每组测试数据输出一个结果，并占一行。

Sample Input

12
5
2310
0

Sample 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;
}