L - Non-Prime Factors

题意
q次询问，每次询问给你一个整数，问该数的因数（非质数）的个数
思路
一开始想这个题目的时候，直接发现可以把一个数质因数分解 $a=\sum _{i=1}^n{p_i}^{q_i}$a=i=1∑n​pi​qi​，那么答案显然就是 $ans=\prod _{i=1}^n(q_i+1)-n$ans=i=1∏n​(qi​+1)−n
但可惜的是，这道题q询问次数太多，如果用合数分解来做的话，会Tle,主要是合数分解复杂度近似 $O\left(n\right)$O(n)
所以，我们可以换一种想法。
对于任意一个整数，它必定可以被拆成两个整数的乘积。所以我们可以枚举因数，然后把2-2e6的数的结果在nln(2e6)的范围打出表。

void solve(){
	int ma = 2e6;
	for(int i = 1; i <= ma; i++){
		int cnt = 2;
		if(flag[i]){///如果i是素数
			cnt--;///那么i不能贡献i*j数的答案
		}
		for(int j = 1; j * i <= ma; j++){
			if(flag[j]) ans[i * j] += cnt - 1;
			else ans[i * j] += cnt;
		}
	}
}

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
bool flag[maxn];
int prime[maxn];
int ans[maxn];
int num = 0;
void getPrime(){
    for(int i = 2; i < maxn; i++){
	flag[i] = true;
    }
    for(int i = 2; i < maxn; i++){
	if(flag[i]){
		prime[++num] = i;
	}
	for(int j = 1; j <= num && i * prime[j] < maxn; j++){
		flag[i * prime[j]] = false;
		if(i % prime[j] == 0){
			break;
		}
	}
    }
}
void solve(){
	int ma = 2e6;
	for(int i = 1; i <= ma; i++){
		int cnt = 2;
		if(flag[i]){
			cnt--;
		}
		for(int j = 1; j * i <= ma; j++){
			if(flag[j]) ans[i * j] += cnt - 1;
			else ans[i * j] += cnt;
		}
	}
}
int main(){
    int q;
    int a;
    getPrime();
    solve();
    scanf("%d", &q);
    while(q--){
	scanf("%d", &a);
	printf("%d\n", ans[a] / 2);
    }
    return 0;
}