思路
题干很简单,但是暴力方法是会超时的
对于数 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; }
这里我们引入一个约数个数定理:
若 ,其中为质数,那么的约数个数,我们简单证明一下:对于来说,它的因子有,而的因子,就是从每个中选择一个的因子来组成的因子,所以根据乘法原理得证。
这样只需要先求一下质数列表,然后看一下质因子的个数就好了。