蓝桥杯2022年第十三届省赛真题-质因数个数

解题思路:

基于算术基本定理
注意事项:

参考代码:

#include<bits/stdc++.h>
int main(){
	long long n,ans = 0,index;
	int sum;
	scanf("%lld",&n);
	for(index = 2;index * index <= n && n != 1;index++){ //index * index <= n这个条件是重点，如果没有这个条件会超时
		sum = 0;
		while(n % index == 0){
			sum++;
			n /= index;
		}
		if(sum){
			ans++;
		}
	}
	if(n != 1){
		ans++; //说明存在一个大于sqrt(n)的质因数，且有且仅有一个，所以要+1
	}
	printf("%lld",ans);
	return 0;
}