Why is this failing for just a corner case? Question link-https://www.hackerearth.com/problem/algorithm/chandu-and-his-interns/description/#c190148

Question

Why is this failing for just a corner case? Question link-https://www.hackerearth.com/problem/algorithm/chandu-and-his-interns/description/#c190148 It ran fine for all the other cases. I took all the three cases where number of divisors could be less than 4. (prime number, 1 and square of prime number)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if 
#define ff first 
#define ss second
#define pii pair<ll int ll int>
#define mp make_pair
#define pb push_back
#define CLEAR(array, value) memset(ptr, value, sizeof(array));
#define si(a)     scanf("%d", &a)
#define sl(a)     scanf("%lld", &a)
#define pi(a)     printf("%d", a)
#define pl(a)     printf("%lld", a)
#define pn        printf("\n")
#define int long long int 

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,x,t,i;
    cin >> n;
    int max=10000009;
    int prime[max];
    int j;

    for(int i=2; i*i<=max; i++)
    {
        if (prime[i]==0)
        {
            for(j=i*i; j<=max; j+=i)
            {
                    prime[j]=1;

            }
        }
    }
    rep(i,n)
    {
        cin >> x;    
        t=sqrt(x);
        if (prime[x]==0)
             cout << "NO" << endl;
        else if ((t*t)==x && prime[t]==0)
             cout << "NO" << endl;
        else
             cout << "YES" << endl;   
    }


}

Answer 1

This appears to be a stack overflow.

You are allocating the prime array on the stack.

The failing test case is for value 9999863 which is close to the end of the prime array.

If you move the line to a non-stack based allocation, e.g. via

static int prime[10000009];

then all tests pass.