C++ 分解一个大数的素因数

题目：

C++ 分解一个大数的素因数

先附上我写的代码：

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n=0;
    static int a[1000000001]={0};             // 把大数组开在了 Data Segment 中
    a[0]=a[1]=1;
    while(cin>>n){
        for(int i=2;i<n;i++){           // 依次遍历2到1000000所有数字
            if(a[i]==0){
                int frequence=n/i;
                for(int j=i;j<=frequence;j++){           // 没有从 2 * i 开始，而是直接从 i * i 开始
                    a[i*j]=1;
                }
            }
        }
        int count=0;
        for(int k=2;k<=n;k+=1){
            if(a[k]==0){
                while(n%k==0){
                    count++;
                    n=n/k;
                }
            }
        }
        cout<<count<<endl;
        
    }
    return 0;
}

注意这里声明数组时用了static，原因见：https://blog.****.net/qq_36770641/article/details/88852924，不再赘述。

这样解决了开大数组报错的问题，然而时间令人着急，而且空间还是超了。。这时我才意识到，没那么简单。。

来看看官方解答：

C++ 分解一个大数的素因数

修改后代码如下：

//
//  54.cpp
//  质因数的个数
//
//  Created by chenmeiqi on 2019/3/27.
//  Copyright © 2019年 chenmeiqi. All rights reserved.
//

#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n=0;
    int count;          // 幂指数个数
    static int a[100001]={0};             // 把大数组开在了 Data Segment 中
    a[0]=a[1]=1;
    while(cin>>n){
        for(int i=2;i<n;i++){           // 依次遍历2到1000000所有数字
            if(a[i]==0){
                int frequence=n/i;
                for(int j=i;j<=frequence;j++){           // 没有从 2 * i 开始，而是直接从 i * i 开始
                    a[i*j]=1;
                }
            }
        }
        count=0;
        for(int k=2;k<=n;k+=1){
            if(a[k]==0){
                while(n%k==0){
                    count++;
                    n=n/k;           // 从被测试数中将该素数分解出来
                }
            }
        }
        if(n!=1){       // 若测试完2到100000内所有素因数，n仍未被分解至1，则剩余的因数一定是一个大于100000素因数
            count++;
        }
        cout<<count<<endl;
        
    }
    return 0;
}

到这里，时间问题似乎解决了。然而问题总是会一个一个来的。请看下面这个：

C++ 分解一个大数的素因数

代码如下：

//
//  55.cpp
//  整除问题
//
//  Created by chenmeiqi on 2019/3/28.
//  Copyright © 2019年 chenmeiqi. All rights reserved.
//

#include <iostream>
#include <array>
#include <cmath>
using namespace std;

array<int, 1001> getPrime(int x){
    array<int, 1001> prime_x={0};
    prime_x[0]=1;
    prime_x[1]=1;
    for (int i=2; i<=x; i++) {
        if (prime_x[i]==0) {
            int frequence=x/i;
            for (int j=i; j<=frequence; j++) {
                prime_x[i*j]=1;
            }
        }
    }
    return prime_x;
}

int main(int argc, const char * argv[]) {
    int n,a;
    array<int, 1001> prime={0};
    prime=getPrime(1000);              // 筛选出 0 ～ 1000 所有素数
    
    while(cin>>n>>a){
        int ans=123123123;         // ans 初始化为一个大整数，为取最小值做准备
        int temp_a=a;           // 临时变量 temp_a 保存 a 的值
        array<int, 1001> exponent_a={0};        // 保存 a 的素因数的指数
        array<int, 1001> exponent_n={0};        // 保存 n 的素因数的指数
      
        for(int i=2;i<=n;i++){
            int temp_n=n;                // 临时变量 temp_n 保存 n 的值
            if(prime[i]==0){
                while (temp_n) {
                    exponent_n[i]+=temp_n/i;
                    temp_n/=i;
                }
            }
        }
        
        for (int i=2; i<=a; i++) {
            if(prime[i]==0){
                while (a%i==0) {            // 找到 a 的素因数
                    exponent_a[i]++;        // 确定指数
                    a/=i;
                }
            }
        }
        

        for(int i=2;i<=temp_a;i++){
            if(exponent_a[i]!=0){           // 若该素数不能从 a 中分解到，即其对应幂指数为 0，则其不影响整除性
                if(exponent_n[i]/exponent_a[i]<=ans){
                    ans=exponent_n[i]/exponent_a[i];
                }
            }
        }
        
        cout << ans <<endl;
    }
    return 0;
}

C++ 分解一个大数的素因数

相关推荐