题解 | 质因数的个数

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>
#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);
		for (int j = i * i; j < maxn; j += i) {
			isprime[j] = false;
		}
	}
}

int numberofprimefactor(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;
			// printf("num:%d\n", number);
			// printf("yingzi:%d\n", factor);
		}
		answer += exponent;
	}
	if (number > 1) { //如果 number 大于 1，说明 number 本身是一个(大于4e4的)质数，将 answer 加 1
		answer += 1;
	}
	return answer;
}

int main() {

	initial();//shai fa

	/*int k;
	while (scanf("%d", &k)!=EOF) {
		printf("%d\n", prime[k - 1]);
	}*/
	int number;
	while (scanf("%d", &number) != EOF) {
		printf("%d\n", numberofprimefactor(number));
	}
	return 0;
}