I am getting wrong answer in POLCONST despite getting correct answer for all test cases that i have tried.
can someone please tell me where am i going wrong??
#include<bits/stdc++.h>
int n=1000000;
using namespace std;
bool prime[1000009];
int sqr[100];
int phi[1000009];
void markmultiples(long long int i)
{
int k;
k=2;
while(i*k<=n)
{
prime[i*k]=false;
k++;
}
}
void sieve()
{
long long int i,l,num,tsum;
memset(prime, true, sizeof(prime));
prime[0]=false;
prime[1]=false;
for(i=2;i<=sqrt(n);i++)
{
if(prime[i]==true)
{
markmultiples(i);
}
}
}
long long int primeFactorize(int temp)
{
long long int i,a,b,k,flag,ans;
phi[1]=0;
phi[2]=1;
phi[3]=2;
i=2;
k=temp;
if(prime[temp]==true)
{
phi[temp]=temp-1;
}
else
{
ans=1;
if(temp%2==0)
{
ans*=phi[2];k=k/2;
}
while(i<=79)
{
i++;
if(prime[i]==true)
{
if(temp%i==0)
{
ans*=phi[i];k=k/i;
}
}
}
phi[temp]=k*ans;
}
return phi[temp];
}
int main()
{
sieve();
long long int t,i,flag=0;sqr[0]=1;
for(i=1;i<32;i++)
{
sqr[i]=sqr[i-1]*2;
}
for(i=2;i<=1000000;i++)
{
phi[i]=primeFactorize(i);
}
cin>>t;
while(t--)
{
int n;
flag=0;
cin>>n;
if(n==1 || n==2)
{
cout<<"Yes"<<endl;
}
else
{
for(i=1;i<32;i++)
{
if(phi[n]==sqr[i])
{
flag=1;
}
}
if(flag==0)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
}
}
return 0;
}