Untitled

#include  <stdio.h>
#include<math.h>
#include<stdbool.h>
#include<string.h>
bool c[463500];
long long int p[10000000];
long long int plen=0;
void sieve()
{
	int i,j;
	memset(c,0,sizeof(c));
	c[0]=c[1]=1;
	for(i=2;i<=463500;i++)
	{
		if(c[i]==1) continue;
		p[plen]=i;
		plen++;
		for(j=i+i;j<=463500;j+=i)
		{
			c[j]=1;
		} 
	}
	return;
}
bool isPrime(int n)
{
	if(n<=463500) return(!c[n]);
	else {
		long long int q=(int)sqrt(n);
		long long int k;
		for(k=0;k<plen&&p[k]<=q;k++){
			if(n%p[k]==0) return false;
			else continue;
		}
		return true;
	}
}
int main(){
    sieve();
    long long int t,n;
    /*
    for(int i=0;i<10;i++){
    	printf("%d ",p[i]);
    }
    printf("\n");
    */
    scanf("%lld",&t);
    while(t--){
    	scanf("%lld",&n);
		if(isPrime(n)) printf("True\n"); 
		else printf("False\n"); 
    }
    return 0;
}