题解 | #质因数的个数#

//土尔逊Torson 编写于2023/05/10
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
                                       //用变量创建数组 建议 用队列 Vector 替代
vector<int> prime07201;                //保存质数

void Initial07201(int MAXN,vector<bool> isPrime07201) {
	for (int i = 0; i < MAXN; ++i) {   //初始化
		isPrime07201[i] = true;
	}
	isPrime07201[0] = false;
	isPrime07201[1] = false;
	for (int i = 2; i < MAXN; ++i) {
		if (!isPrime07201[i]) {        //非质数则跳过
			continue;
		}
		prime07201.push_back(i);
		for (int j = i*i; j < MAXN; j += i) {
			isPrime07201[j] = false;       //质数的倍数为非质数
		}
	}
	return;
}

int main() {
	const int MAXN = sqrt(1e9) + 1;
	vector<bool> isPrime07201;
	for (unsigned int i = 0; i < MAXN; ++i) { //保存队列
		isPrime07201.push_back(true);
	}
	Initial07201(MAXN,isPrime07201);
	int n;

	while (scanf("%d", &n) != EOF) {
		int answer = 0;
		for (int i = 0; i < prime07201.size() && prime07201[i] < n; ++i) {
			int factor = prime07201[i];
			while (n % factor == 0) {    //不断试除
				n /= factor;
				answer++;
			}
		}
		if (n > 1) {                  //还存在一个质因数
			answer++;
		}
		printf("%d\n", answer);
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")