16 分解素因数

题目来源和说明

本题来源于2007年清华大学计算机研究生机考真题。

题目描述

求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。

输入描述

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出描述

对于每组数据，输出N的质因数的个数。

样例

输入：
120

输出：
5

简要分析

我们利用上篇博客中所讲的素数筛选法预先筛选出所有可能在题目所给定数据范围内称为素因数的素数。并在程序输入待处理数字n时，依次遍历所有小于n的素数，判断死否为n的因素。若确定某素数为n的因数，则通过试除确定其对应的幂指数。最后求出各个幂指数的和即为所求。

1. 利用素数筛选法筛出0到sqrt(1e5)区间内所有素数（因为n最多只存在一个大于sqrt(n)的素因数，否则两个大于sqrt(n)的因数相乘必大于n。基于这个理论我们不必测试sqrt(n)到n的素数）。
2. 输入n
3. 依次测试步骤1中得到的素数能否整除n,若能则表明该素数为它的一个素因数。
4. 不断将n除以该素数，知道不能再被整除为止，同时统计其幂指数。
5. 若在完成某个素数的幂指数统计后，n变成了1，说明n的所有素因数全部被分解出来，这样就不用取遍历后续的素数了，分解活动提前终止。
6. 若遍历、测试、分解完所有预处理出来的素数，n依旧没被成0，说明存在一个大于他的根号的因数，那么最后加上即可

C++ 代码

#include<iostream>
using namespace std;

bool mark[100001];
int prime[100001];
int primeSize;

void init() { //用素数筛选出2到100000内的所有素数
    primeSize=0;
    for(int i=2;i<=100000;i++) {
        if(mark[i]==true) continue; //已经被标记
        prime[primeSize++]=i;
        for(int j=i*i;j<=100000;j+=i) {
            mark[j]=true; //被标记
        }
    }
}

int main() {
    init();
    int n;
    while(scanf("%d",&n)!=EOF) {
        int ansPrime[30]; //按照顺序保存分解出来的素因数
        int ansSize=0; //分解出来素因数的个数
        int ansNum[30]; //保存分解出来的素因数对应的幂指数
        for(int i=0;i<primeSize;i++) { //依次测试每一个素数
            if(n%prime[i]==0) { //如果能被整除
                ansPrime[ansSize]=prime[i]; //该素数为其素因数
                ansNum[ansSize]=0; //初始化为0
                while(n%prime[i]==0) {
                    ansNum[ansSize]++;
                    n/=prime[i];
                }
                ansSize++;
                if(n==1) break; //若被分解乘1，则分解提前终止
            }
        }
        if(n!=1) { //若测试完2到100000内所有素因数，n仍未被分解成1，则剩余的因数一定是n大于100000的素因数
            ansPrime[ansSize]=n;
            ansNum[ansSize++]=1; //其幂指数为1
        }
        int ans=0;
        for(int i=0;i<ansSize;i++) {
            ans+=ansNum[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

同类题目

1. 整除问题

简要分析

这道题目对我来说难度很大，但是好在再分解素数这一节还有些提示。这里详细记录一下。

要解决这个问题，首先注意到这么一个问题，n!和a的k次方可能数值非常巨大，而不能被int（甚至long long）保存，也就是说不能用求余操作判断他们是否存在整除关系。那么，我们不得不从整除的特征入手，转而思考若整数a能够整除b则那么之间有什么关系？我们不当对a和b分解素因数：

则b除以a能偶表示成：

因为两个质数是互质的，因此如果p1和p2不相等的话，那么比不可能被整除，所以如果b/a是整数的话，比如满足：

（1）a分解出来素数，b必能分解出来

（2）且该素因数再b中对应的幂指数比不小于再a中的幂指数。

现在，我们假设x=n!,y=a^k，我们对n!于a分解素因数，令：

相应的我们也可以得到a的k次方的素因数分解情况为：

即我们要确定最大的非负整数k，使得a中任意素因数的幂指数的k倍依旧小于或等于该素因数再x中对应的幂指数。要求得到该k，我们只需依次测试a中每一个素因数，确定b中该素因数对应的幂指数是a中幂指数的几倍（利用整除法），这样所有倍数中最小的那个即为我们要求的k.

分析到这里，剩余的工作似乎只剩下对a和n!分解素因数，对a分解素因数我们再上一题中已经探讨过了。那么对于n!呢？千万不要指望将n!计算出来后再类似a一样对其分解质因数，由于n!数值非常巨大（当n>30时），想要这样操作几乎是不可能的，那么我们该如何对其分解素因数呢？是考虑n！中含有素因数p的个数，即确定素因数p对应的幂指数。我们容易得知，n!中包含了1到n区间内所有整数的乘积，这些乘积中每一个p的倍数都将对n！供应一个p的因子，且我们知道再1到n中p的倍速共有n/p个。具体过程如下：

1. 计数器清零
2. 计算n/p，有n/p个整数可以向n!提供一个p因子
3. 计算n/（p* p)，有n/(p* p)个整数可以向n!提供两个p因子，但是他们再之前的步骤中（p的倍数比包括p* p的倍数）每个数都已经向计数器累加1个p因子，所以他们还需要向计数器共享n/(p * p)个因子。 依次累加p的更高次的倍数能够再提供的素因子数，即每次向计数器累加n/p^k，直到n/p^k变成0，表示没有整数能够提供更多的p因子，关于p的分解结束。 完成完这些步骤后就能计算出n!中所有的p因子数目，即计数器中累加的结果即为素因数p的幂指数。

注：该分析来自王道考研！

C++代码

#include<iostream>

using namespace std;

bool mark[1010];
int prime[1010];
int primeSize;

void init() {
    primeSize=0;
    for(int i=2;i<=1000;i++) {
        if(mark[i]) continue;
        prime[primeSize++]=i;
        for(int j=i*i;j<=1000;j+=i) {
            mark[j]=true;
        }
    }
}
int cnt[1010]; //cnt[i]用来表示n!分解素数因数后，素因子prime[i]所对应的的幂指数
int cnt2[1010]; //用来表示a分解成素因数后，素因子prime[i]所对应的幂指数。
int main() {
    int n,a;
    init();
    while(scanf("%d%d",&n,&a)==2) {
        for(int i=0;i<primeSize;i++) {
            cnt[i]=cnt2[i]=0; //将两个计数器清零
        }
        //分解n!
        for(int i=0;i<primeSize;i++) {//对n！分解素因数，遍历每一个素数
            int t=n;
            while(t) { //确定素数prime[i]再n中的因子数，每一个prime[i]的倍数贡献倍数个素数
                cnt[i]+=t/prime[i];
                t=t/prime[i];
            }
        }
        //分解a
        int ans=1e6+10; //答案初始化一个大整数，为取最小值做准备
        for(int i=0;i<primeSize;i++) {
            while(a%prime[i]==0) {
                cnt2[i]++;
                a=a/prime[i];
            } //计算a中素因数prime[i]对应的幂指数
            if(cnt2[i]==0) continue;//若该素数不能从a中分解到，即对应的幂指数为0，不影响正出行
            if(cnt[i]/cnt2[i]<ans) 
                ans=cnt[i]/cnt2[i];
        }
        printf("%d",ans);
    }
    return 0;
}

2. 约数的个数

简要分析

C++代码

#include<iostream>
using namespace std;

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        for(int i=0;i<n;i++) {
            int x,res;
            scanf("%d",&x);
            res=0;
            int j;
            for(j=1;j*j<x;j++) {
                if(x%j==0) res+=2;
            }
            if(j*j==x) res++;
            printf("%d\n",res);
        }
    }
    return 0;
}