• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • 试除法求质因子
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

求正整数 N（N>1）的质因数的个数。

相同的质因数需要重复计算。

如 120=2×2×2×3×5，共有 5 个质因数。

输入格式

输入可能包含多组测试数据。

每组数据占一行，包含一个正整数 N。

输出格式

对于每组输入，输出一行结果表示 N 的质因数的个数。

数据范围

1 每个输入最多包含 100 组测试数据。

输入样例：

120

输出样例：

5

试除法求质因子

分析

代码

#include
#include
typedef long long LL;

using namespace std;
LL n, res = 0;
int main()
{
	while(cin >> n)
	{
	    res = 0;
		for(int i = 2; i <= n / i; i++)
		{
			if(n % i == 0)
			{
				while(n % i == 0)
				{
					res ++;
					n /= i;
				}
			}
		}	
		if(n > 1) res++;
		
		printf("%lld\n", res);
	}
	return 0;
} 

时间复杂度

参考文章