王道机试指南 习题6.7 约数的个数

题目：

思路：

暴力解法会超时，不能全部遍历。

对于数num，可以只依次检查1~sqrt(num)之间的数j能否整除num：

对于小于sqrt(num)的数j，如果num%j==0且j*j!=num，则必定还存在一个大于sqrt(num)的数j0，使得j*j0=num,算两个约数；如果num%j==0且j*j==num，说明j==j0，算一个约数。

代码：

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        vector<int> arr;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            arr.push_back(x);
        }
        for(int i=0;i<n;i++){
            int count=0;
            int num=arr[i];
            for(int j=1;j<=sqrt(num);j++){//对于数num，可以只依次检查1~sqrt(num)之间的数j能否整除num
                if(num%j==0 && j*j!=num) {//对于小于sqrt(num)的数j,如果num%j==0且j*j!=num,则必定还存在一个大于sqrt(num)的数j0,使得j*j0=num,算两个约数
                    count=count+2;
                }
                else if(num%j==0 && j*j==num){//如果num%j==0且j*j==num,说明j==j0，算一个约数
                    count=count+1;
                }
            }

            cout<<count<<endl;
        }    
    }
    return 0;
}

运行结果：