文章

16

粉丝

76

获赞

3

访问

9.6k

头像
质因数个数 题解:C++
P1156 清华大学上机题
发布于2024年3月13日 18:31
阅读数 578

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int prim[maxn];//存素数
bool p[maxn]={0};//标记
int num=1;//从prim【1】开始存素数
void find(){//筛选素数法
    for(int i=2;i<maxn;i++){
        if(p[i]== false){
            prim[num++]=i;
            prim[0]++;//prim【0】存素数prime数组的长度
            for(int j=i;j<maxn;j+=i)
                p[j]= true;
        }
    }
}
int main(){//求质因子个数
    find();
    int n;
    while(cin>>n){
        int ans=0;
        for (int i = 0; i < prim[0]; ++i){//分解质因子
            while(n%prim[i]==0){//说明n除以prim[i]能除尽,则prim[i]为n的质因子
                n/=prim[i];
                ans++;//质因子个数加1
            }
        }
        if(n>1) ans++;//表明除到最后剩的不为1时,质因子+1,若为1则1不加
        cout<<ans<<endl;
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发