AOJ 780.分解质因数

599


题目



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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论