Splitting Bill O(1) per case with Precomputation (C++)

#include <iostream>

using namespace std;

int* sieveOfEratosthenes(int n) {
    int* sieve = new int[n + 5];
    for (int i = 0; i < n + 5; i++)
        sieve[i] = 1;
    sieve[0] = 0;
    for (int i = 2; i * i < n + 5; i++)
        for (int j = i * i; j < n + 5; j += i)
            sieve[j] = i;
    return sieve;
}

int main() {
    int* sieve = sieveOfEratosthenes(1000000);

    int testCases;
    cin >> testCases;
    for (int testCase = 1; testCase <= testCases; testCase++) {
        int n;
        cin >> n;
        cout << n / sieve[n] - sieve[n] << '\n';
    }

    return 0;
}