题解 | #质因数的个数#

#include<iostream>
#include<math.h>
#include<vector>

using namespace std;

const int MAXN = 4e4;

bool isPrime[MAXN];

vector<int> prime;

//初始化操作

void Initial() {
	//初始化辅助数组
	for(int i = 0; i < MAXN; ++i) {
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for(int i = 2; i < MAXN; ++i) {
		if(!isPrime[i]) {
			continue;
		}
		prime.push_back(i);
		if(i > MAXN / i) {
			continue;
		}
		for(int j = i * i; j < MAXN; j += i) {    //质数的倍数是非质数
			isPrime[j] = false;
		}
	}
}

//短除法求质因数
int NumberOfPrimeFactors(int number) {
	int answer = 0;
	for(int i = 0; i < prime.size(); ++i) {
		int factor = prime[i];     //质数
		if(number < factor) {   //如果输入的整数小于第一个质数，说明改整数无法被分解为质因数相乘的形式
			break;
		}
		int exponent = 0;   //记录质因子的个数
		while(number % factor == 0) {    //试除
			exponent++;
			number /= factor;
		}
		answer += exponent;
	}
	if(number > 1) {   //分解到不能分解时，如果number大于1，说明还存在一个质因子
		answer += 1;
	}
	return answer;
}

int main() {
	//调用筛选法
	Initial();
	int number;
	while(scanf("%d",&number) != EOF) {  //多组样例输入
		printf("%d\n",NumberOfPrimeFactors(number));
	}
	return 0;
}