以前貌似写过这种题目,那时候貌似还感觉很难,今天再写了一遍发现就这样把...
设要分解的数为n
- 首先打表,将一定范围内的质数表打出来
- 将n从最小的质数开始取模,要求是这个质数必须小于等于当前的n
- 当模为0时,并且小于当前的n,这个质数就是分解出来的质因数,将其保存,然后将n的值除以这个质数,循环步骤2.
- 若当前的质数等于了当前的n,那么就循环结束,最后一个分解的数就是当前的n(也可以说是这个质数).
代码如下:
#include <bits/stdc++.h>
using namespace std;
int prime[1300];
int cnt_prime = 0;
bool isPrime(int n){
for(int i=2;i<=sqrt(n);i++) {
if(n%i==0) return false;
}
return true;
}
void solve(int n) {
cout << n <<"=";
int t = n;
for(int i=0;i<cnt_prime;) {
if(t>prime[i]&&t%prime[i]==0) {
cout << prime[i] << "*";
t/=prime[i];
i=0;
}
else if(t==prime[i]) {
cout << t;
break;
}
else {
i++;
}
}
cout << endl;
}
int main() {
for(int i=2;i<10000;i++) {
if(isPrime(i)) prime[cnt_prime++]=i;
} //打表
int n;
cin >> n;
solve(n);
return 0;
}
2 comments
不错
实力技术派啊