约数的个数

思路

题干很简单，但是暴力方法是会超时的

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

#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;
}

这里我们引入一个约数个数定理：

若 ，其中为质数，那么的约数个数，我们简单证明一下：对于来说，它的因子有，而的因子，就是从每个中选择一个的因子来组成的因子，所以根据乘法原理得证。

这样只需要先求一下质数列表，然后看一下质因子的个数就好了。