约数的个数

http://t.cn/Aip7dTUp

描述

输入n个整数,依次输出每个数的约数的个数

输入描述：

输入的第一行为N，即数组的个数(N<=1000) 接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)

输出描述：

可能有多组输入数据，对于每组输入数据， 输出N行，其中每一行对应上面的一个数的约数的个数。

示例1

输入：

5
1 3 4 6 12

输出：

1
2
3
4
6

代码一：

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

const int N = sqrt(1e4) + 10;

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 NumberOfFactor(int number) {
	int answer = 1;
	for (int i = 0; i < prime.size(); ++i) {
		int exponent = 0;
		while (number % prime[i] == 0)
		{
			exponent++;
			number /= prime[i];
		}
		answer *= exponent + 1;//默认包含约数1
	}
	if (number > 1)
		answer *= 2;
	return answer;
}

int main() {
	Initial();
	int n;
	while (cin >> n)
	{
		if (n == 0)
			break;
		for (int i = 0; i < n; ++i) {
			int number;
			cin >> number;
			printf("%d\n", NumberOfFactor(number));
		}
	}
	return 0;
}

代码2：

//i*i<num的形式，数值稳定性更好
#include<iostream>
using namespace std;
int numOfDivisor(int num)
{
	int ans = 0;
	int i;
	for (i = 1; i*i<num; i++)
	{
		if (num%i == 0)
			ans += 2;
	}
	if (i*i == num) ans++;
	return ans;
}
int main()
{
	int n, num;
	while (cin >> n)
	{
		for (int i = 0; i<n; i++)
		{
			cin >> num;
			cout << numOfDivisor(num) << endl;
		}
	}
	return 0;
}