题解 | 约数的个数

//由算数基本定理可知，对于一个大于的正整数可以分解质因数：
//n=p1^a1×p2^a2×p3^a3*…*pk^ak
//则由约数个数定理可知的正约数有个
//(a1+1)(a2+1)(a3+1)…(ak+1)
//1.筛法求质因子          initial()
//2.质因子(指数+1)相乘    answer *= exponent + 1;
//3.if (number >1) {       //说明有一个大于根号n的因子 ,一个质因子是一次方,1+1=2,故乘2.
//       answer *= 2;
//   }
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
const int maxn = 4e4;
bool isprime[maxn];
vector<int>prime;

void initial() {
    for (int i = 0; i < maxn; i++) {
        isprime[i] = true;
    }
    isprime[0] = false;
    isprime[1] = false;
    for (int i = 2; i < maxn; i++) {
        if (!isprime[i]) {
            continue;
        }
        prime.push_back(i);
        for (int j = i * i; j < maxn; j += i) {
            isprime[j] = false;
        }
    }
}

int numberofprimefactor(int number) {
    //int answer = 0;
    int answer = 1;
    for (int i = 0; i < prime.size(); i++) {
        int factor = prime[i];
        if (number < factor) {
            break;
        }
        int exponent = 0;
        while (number % factor == 0) {
            exponent++;
            number /= factor;
            //printf("num:%d\n", number);
            //printf("yingzi:%d\n", factor);

        }
        //answer += exponent;
        answer *= exponent + 1;
    }
    if (number >1) {       //说明有一个大于根号n的因子 ,一个质因子是一次方,1+1=2,故乘2.
        //answer += 1;
        answer *= 2;
    }
    return answer;
}


int main() {

    initial();//shai fa
    int n;
    while(scanf("%d", &n)!=EOF){
		  for (int i = 0; i < n; i++) {
              int number;
              scanf("%d", &number) ;
              printf("%d\n", numberofprimefactor(number));
         }
	}
    return 0;
}