题解 | #约数的个数#

• 筛数法，先求质数表，再根据表判断质因数，统计质因数的指数
• 根据因数个数定理：因数总数=（各质因数指数+1）的乘积

#include<iostream>
#include<vector>
using namespace std;
const int maxn=4e4;
vector<int>prime;

void initial(){//构造质数表
    int shaishu[maxn];
    shaishu[0]=shaishu[1]=0;
    for(int i=2;i<maxn;i++)shaishu[i]=1;
    for(int i=2;i<maxn;i++){
        if(shaishu[i]==0)continue;
        else{
            prime.push_back(i);
            if(i>maxn/i)continue;
            for(int j=i*i;j<maxn;j+=i){
                shaishu[j]=0;
            }
        }
    }
}
int main(){
    initial();
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            int sum=1;
            for(int i=0;i<prime.size()&&prime[i]<=x;i++){
                int k=0;//质因数的指数
                while(x%prime[i]==0){
                    k++;
                    x=x/prime[i];
                }
                sum=sum*(1+k);
            }
            if(x!=1)sum=sum*2;
            printf("%d\n",sum);
        }
    }
    return 0;
}

• 直接计数：因数总是成对出现，只考虑i²<n的一半因数，注意完全平方数时，有一个单独因数

#include<iostream>
#include<vector>
using namespace std;
const int maxn=4e4;
vector<int>prime;

int getans(int x){//求因数总数
    int sum=0;
    int i;
    for(i=1;i*i<x;i++){
        if(x%i==0)sum++;
    }
    sum*=2;
    if(i*i==x)sum++;
    return sum;
 
}
int main(){

    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
          
            printf("%d\n",getans(x));
        }
    }
    return 0;
}