A50244.小午的质因子统计 题解

$O(\sqrt{n})$ 的质因数分解相信大家人人都会，就不赘述了。

但是 $O(n\sqrt{n})$ 在这题会超时，所以我们需要 $O(n \log n)$ 计算。

考虑到根号算法耗时在寻找质因子的时候，所以筛法记录每个数的最小质因子。采用埃氏筛。

时间复杂度：$O(n \log n)$

空间复杂度：$O(n)$

Code:

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[1000005],p[1000005];
bool isp[1000005],vis[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    isp[0]=isp[1]=true;
    for(int i=2;i<=1000000;i++){
        if(!isp[i]){
            for(int j=i;j<=1000000;j+=i){
                if(p[j]==0) p[j]=i;
                else p[j]=min(i,p[j]);
            }
        }
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(a[i]>1){
            vis[p[a[i]]]=true;
            a[i]/=p[a[i]];
        }
    }
    for(int i=1;i<=1000000;i++) if(vis[i]) ans++;
    cout<<ans;
    return 0;
}