质因数的个数

http://t.cn/Aip7J0Oo

描述

求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述：

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出描述：

对于每组数据，输出N的质因数的个数。

示例1

输入：

120

输出：

5

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;

const int N = sqrt(1e9) + 1;
vector<int> prime;
vector<bool> isPrime(N, true);

void Initial() {
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i < N; ++i) {
		if (!isPrime[i])//非质数则跳过
			continue;
		prime.push_back(i);
		for (int j = i * i; j < N; j += i)
			isPrime[j] = false;
	}
	return;
}

int main() {
	Initial();
	int n;
	while (cin >> n)
	{
		int answer = 0;
		for (int i = 0; i < prime.size() && prime[i] < n; ++i) {
			int factor = prime[i];
			while (n % factor == 0)
			{
				n /= factor;
				answer++;
			}
		}
		if (n > 1)//还存在一个质因数
			answer++;
		printf("%d\n", answer);
	}
	return 0;
}