AOJ 780.分解质因数

228


题目



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