赛后补题L - Non-Prime Factors

在许多编程比赛中，我们被要求找到（或计算）整数 ii 的质因数。这很无聊。这一次，让我们计算整数 ii 的非素因子的数量，记为 NPF(i)。 例如，整数 100100 有以下九个因数：\{ 1, \underline{2}, 4, \underline{5}, 10, 20, 25, 50, 100\}{1, 2​ ,4, 5​,10,20,25,50,100}。下划线的两个是 100100 的质因数，其余是非质因数。因此，NPF(100) = 77。 输入 第一行包含一个整数 QQ (1 \le Q \le 3\cdot 10^61≤Q≤3⋅10 6）表示查询的数量。接下来的每一 QQ 行包含一个整数 ii (2 \leq i \leq 2\cdot 10^62≤i≤2⋅10 6）。 输出 对于每个查询 ii，打印 NPF(i) 的值。 警告 I/O 文件很大。请使用快速 I/O 方法。

题意：给定一个数n，求这个数有多少个合数因子

#include 
using namespace std;
const int N=2000010;
int primes[N];
int cnt;
bool st[N];
void getprime(int n)
{
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (st[i] == false)
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
int ans[N];
void init()
{
    for(int i=2;i<=N;i++)
    {
        if(!st[i])
        continue;
        for(int j=i;j<=N;j+=i)
        {
            ans[j]++;
        }
    }
 
}
int main()
{
    getprime(N);
    init();
    int q, n;
    cin >> q;
 
    while (q--)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n",ans[x]+1);
    }
    return 0;
}