文章

108

粉丝

0

获赞

99

访问

6.1k

头像
质因数个数 题解:
P1156 清华大学上机题
发布于2026年2月1日 10:57
阅读数 51

#include<iostream>
#include<vector>
using namespace std;

int n;
vector<int> prim;

bool check(int n)
{
	if(n==1)
		return false;
	if(n==2)
		return true;
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
			return false;
	return true;
}

void init()
{
	for(int i=2;i<=300000;i++)
		if(check(i))
			prim.push_back(i);
}

int work()
{
	int res=0,copy=n;
	for(int i=0;i<prim.size();i++)
	{
		int x=prim[i];
		if(copy%x==0)
		{
			int res_0=0;
			while(copy%x==0)
			{
				res_0++;
				copy/=x;
			}
			res+=res_0;
		}
	}
	if(copy!=1)
		res++;
	return res;	
}

int main()
{
	init();
	while(cin>>n)
	{
		if(check(n))
			cout<<1<<endl;
		else
			cout<<work()<<endl;
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发