算术基本定理

Star_LIcsAy · 2021-10-01 16:40:19 · 个人记录

又称唯一分解定理。

其意思为：所有大于 1 的正整数都可以被唯一分解为若干个质因数的积。

如：6=2×3,60=2×2×3×5=2^2×3^1×5^1.

例题：P2043 质因子分解

• 求 n! 的质因子分解。我们可以证明其中不会包含比n大的质因子且小于n的质数至少作为因子存在一次，所以使用线性筛法求得小于等于 n 的质数，再分别计数即可。

• 关于计数方式。

  由容斥原理可得，对于 n! 求 P 因子的个数，我们可以转化为求该因子在 n 范围以内的倍数个数。对于 P^2 的倍数，由于里面包含两个 P，所以我们按照一般思想应该先减去，再加上它的二倍。但这是可以合并同类项的，合并之后转化为再加上 P^2 的倍数个数。该结论可以推广到 P 的所有次方。

  即：

  \dfrac{n}{P}-\dfrac{n}{P^2}+\dfrac{2n}{P^2}-\dfrac{2n}{P^3}+\dfrac{3n}{P^3}+... =\dfrac{n}{P}+\dfrac{n}{P^2}+\dfrac{n}{P^3}+...

• 时间复杂度：线性筛法 O(n)

#include<bits/stdc++.h>
using namespace std;

int p[5005];
bool st[10005];
int k=0;

void get(int x){//线性筛法
    for(int i=2;i<=x;i++){
        if(!st[i])
            p[++k]=i;
        for(int j=1;j<=k && p[j]*i<=x;j++){
            st[p[j]*i]=true;
            if(!i%p[j])
                break;
        }
    }
    return ;
}

int main(){
    int n;
    scanf("%d",&n);
    get(n);
    for(int i=1;i<=k;i++){
        printf("%d ",p[i]);
        int cnt=p[i];
        int ans=0;
        while(cnt<=n){//计算质因子个数
            ans+=n/cnt;
            cnt*=p[i];
        }
        printf("%d\n",ans);
    }
    return 0;
} 

• 此外，质数与合数还有一些其他性质，比如：

  • 对于任意一个合数 n，它的最大质因子一定不大于 \sqrt{n} .

  • 在 n 以内，质数的个数大约为 n/ln\ n.