思路

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

对于数 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;
}

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

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

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