以前貌似写过这种题目,那时候貌似还感觉很难,今天再写了一遍发现就这样把...

设要分解的数为n

  1. 首先打表,将一定范围内的质数表打出来

  2. 将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;
}
最后修改：2020 年 03 月 07 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏