计算一个数的约数的个数

题目描述
输入n个整数,依次输出每个数的约数的个数
输入描述:
输入的第一行为N,即数组的个数(N=1000)
接下来的1行包括N个整数,其中每个数的范围为(1=Num=1000000000)
当N=0时输入结束。
输出描述:
可能有多组输入数据,对于每组输入数据,
输出N行,其中每一行对应上面的一个数的约数的个数。
示例1
输入
5
1 3 4 6 12
输出
1
2
3
4
6
思路:这题其实想法很简单,但是按照平常解法,时间复杂度过大,会运行超时。这里采用一种优化的写法,大大降低了时间复杂度。先上代码,后面有说明。

#includebits/stdc++.h
using namespace std;
int count(long long a)
{
	int sum=0;
	for(int i=1;i*i=a;i++)
	{
		if(a%i==0i*ia) //是因子且小于sqrt(a),则另一个因子大于sqrt(a),故一次加两个 
			sum+=2;
		else if(i*i==a)//两个因子相同,所以只加一次 
			sum++;
	}
	return sum;
}
int main()
{
	int n;
	while(cinn)
	{
		if(n==0)
			break;
		long long a;
		while(n--)
		{
			cina;
			coutcount(a)endl;
		}
	}
} 

说明:因为小于sqrt(n)的数i如果能整除n,则必定还有一个sqrt(n)的因数j,使得ij=n。+2是把这两个因数都算进去了。最后如果ii=n,说明有两个相同的i是因数,只算一个。

最新回复(0)
/jishujpXo4FQc_2FQeXdc2i6WPYe1Ux_2FuRqTXbVw8HNcA3XU9w_3D4833785
8 简首页