#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#define MAX 1000010
#define LMT 1000000
#define END 100000000 //9
bool a[MAX];
int count;
void seive(bool a[],int lmt);
int gen[10000000];
bool final[END];
int main(void)
{
long long int i,j,n,q,temp,length,val;
for(i=2;i<=LMT;i++)
a[i]=1;
seive(a,LMT);
for(i=2;i<=LMT;i++)
if(a[i])
count+=1; // total number of prime numbers till 1000000
int prime[count]; // array of that size and storing all these prime numbers in array prime[]
length=0;
for(i=0;i<=LMT;i++)
{
if(a[i])
{
prime[length]=i;
length+=1;
}
}
long long int genlen=0;
int flag=0;
for(i=0;i<length;i++) // now making gen[] to store all possible 2 multiples of these prime numbers stored
{ // in prime[] ,if only product of these two primes is <=1000000
temp=(long)(prime[i]);
for(j=i;j<length;j++)
{
if((temp*prime[j])>LMT && i==j)
{
flag=1;
break;
}
if((temp*prime[j])>LMT)
{
break;
}
gen[genlen]=temp*prime[j];
genlen+=1;
}
if(flag)
break;
}
for(i=0;i<genlen;i++) // now marking all these two times multiples of each primes as 1 bcoz , all these result
final[gen[i]]=1; // can directly decompose into two prime multiples
scanf("%lld %lld",&n
,&q
); int a[n];
for(i=0;i<n;i++)
for(i=0;i<n;i++) // now other set of numbers which can be decompose into two prime multiples will be
{ // product of given array number into one of these generated number(gen[i]),and all its
// multiples ,till its less than 1000000. follow these for each given number with each generated array number(gen[i])
for(j=0;j<genlen;j++)
{ // for e.g = given array = 3 2 6
temp=(long)(gen[j]); // eg generated prime= 4 5 9 15
if((temp*gen[j])>LMT) // now mark product of given array(a[i]) and generated array(gen[i])=(3*4=12)
break; // bcoz 12 can be decompose to 4 (dividing by 3 ) which is product of two primes
while((a[i]*temp)<=LMT) // process doesnot stops, we will multiply (((12*3)*3)*3.... <=1000000
{ // bcoz all these results can be divided by any number of times by 3 and atlast becomes 4 which is product of two primes
final[a[i]*temp]=1; // same for each number.
temp=(long)(temp*a[i]);
}
}
}
while(q--)
{
if(val==0)
else
{
if(final[val])
else
}
}
return 0;
}
void seive(bool a[],int lmt)
{
long int i,j,temp,temp1;
for(i
=2;i
<=sqrt(lmt
);i
++) {
if(a[i])
{
temp=(long)i;
for(j=2;temp*j<=lmt;j++)
{
temp1=(long)i;
a[temp1*j]=0;
}
}
}
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdGRib29sLmg+CiNkZWZpbmUgTUFYIDEwMDAwMTAKI2RlZmluZSBMTVQgMTAwMDAwMAojZGVmaW5lIEVORCAxMDAwMDAwMDAgLy85CmJvb2wgYVtNQVhdOwppbnQgY291bnQ7CnZvaWQgc2VpdmUoYm9vbCBhW10saW50IGxtdCk7CmludCBnZW5bMTAwMDAwMDBdOwpib29sIGZpbmFsW0VORF07CmludCBtYWluKHZvaWQpCnsKbG9uZyBsb25nIGludCBpLGosbixxLHRlbXAsbGVuZ3RoLHZhbDsKZm9yKGk9MjtpPD1MTVQ7aSsrKQphW2ldPTE7CnNlaXZlKGEsTE1UKTsKZm9yKGk9MjtpPD1MTVQ7aSsrKQppZihhW2ldKQpjb3VudCs9MTsgICAgICAgICAgICAgIC8vIHRvdGFsIG51bWJlciBvZiBwcmltZSBudW1iZXJzIHRpbGwgMTAwMDAwMAppbnQgcHJpbWVbY291bnRdOyAgICAgICAvLyBhcnJheSBvZiB0aGF0IHNpemUgYW5kIHN0b3JpbmcgYWxsIHRoZXNlIHByaW1lIG51bWJlcnMgaW4gYXJyYXkgcHJpbWVbXQpsZW5ndGg9MDsKZm9yKGk9MDtpPD1MTVQ7aSsrKQp7CmlmKGFbaV0pCnsKcHJpbWVbbGVuZ3RoXT1pOwpsZW5ndGgrPTE7Cn0KfQpsb25nIGxvbmcgaW50IGdlbmxlbj0wOyAgICAgICAgCmludCBmbGFnPTA7CmZvcihpPTA7aTxsZW5ndGg7aSsrKSAgICAgICAgLy8gbm93IG1ha2luZyBnZW5bXSB0byBzdG9yZSBhbGwgcG9zc2libGUgMiBtdWx0aXBsZXMgb2YgdGhlc2UgcHJpbWUgbnVtYmVycyBzdG9yZWQKewkJCQkJCQkvLyBpbiBwcmltZVtdICxpZiBvbmx5IHByb2R1Y3Qgb2YgdGhlc2UgdHdvIHByaW1lcyBpcyA8PTEwMDAwMDAKdGVtcD0obG9uZykocHJpbWVbaV0pOwpmb3Ioaj1pO2o8bGVuZ3RoO2orKykKewppZigodGVtcCpwcmltZVtqXSk+TE1UICYmIGk9PWopCnsKZmxhZz0xOwpicmVhazsKfQppZigodGVtcCpwcmltZVtqXSk+TE1UKQp7CmJyZWFrOwp9CmdlbltnZW5sZW5dPXRlbXAqcHJpbWVbal07Cmdlbmxlbis9MTsKfQppZihmbGFnKQpicmVhazsKfQpmb3IoaT0wO2k8Z2VubGVuO2krKykgICAgLy8gbm93IG1hcmtpbmcgYWxsIHRoZXNlIHR3byB0aW1lcyBtdWx0aXBsZXMgb2YgZWFjaCBwcmltZXMgYXMgMSBiY296ICwgYWxsIHRoZXNlIHJlc3VsdApmaW5hbFtnZW5baV1dPTE7ICAgICAgICAgLy8gY2FuIGRpcmVjdGx5IGRlY29tcG9zZSBpbnRvIHR3byBwcmltZSBtdWx0aXBsZXMKc2NhbmYoIiVsbGQgJWxsZCIsJm4sJnEpOwppbnQgYVtuXTsKZm9yKGk9MDtpPG47aSsrKQpzY2FuZigiJWQiLCZhW2ldKTsKZm9yKGk9MDtpPG47aSsrKSAgICAgICAgICAgIC8vIG5vdyBvdGhlciBzZXQgb2YgbnVtYmVycyB3aGljaCBjYW4gYmUgZGVjb21wb3NlIGludG8gdHdvIHByaW1lIG11bHRpcGxlcyB3aWxsIGJlCnsgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBwcm9kdWN0IG9mIGdpdmVuIGFycmF5IG51bWJlciBpbnRvIG9uZSBvZiB0aGVzZSBnZW5lcmF0ZWQgbnVtYmVyKGdlbltpXSksYW5kIGFsbCBpdHMKICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vIG11bHRpcGxlcyAsdGlsbCBpdHMgbGVzcyB0aGFuIDEwMDAwMDAuIGZvbGxvdyB0aGVzZSBmb3IgZWFjaCBnaXZlbiBudW1iZXIgd2l0aCBlYWNoIGdlbmVyYXRlZCBhcnJheSBudW1iZXIoZ2VuW2ldKQpmb3Ioaj0wO2o8Z2VubGVuO2orKykKeyAgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBmb3IgZS5nID0gZ2l2ZW4gYXJyYXkgPSAzIDIgNgp0ZW1wPShsb25nKShnZW5bal0pOyAgICAgICAgIC8vIGVnIGdlbmVyYXRlZCBwcmltZT0gNCA1IDkgMTUKaWYoKHRlbXAqZ2VuW2pdKT5MTVQpICAgICAgICAvLyBub3cgbWFyayBwcm9kdWN0IG9mIGdpdmVuIGFycmF5KGFbaV0pIGFuZCBnZW5lcmF0ZWQgYXJyYXkoZ2VuW2ldKT0oMyo0PTEyKQpicmVhazsgICAgICAgICAgICAgICAgICAgICAgIC8vIGJjb3ogMTIgY2FuIGJlIGRlY29tcG9zZSB0byA0IChkaXZpZGluZyBieSAzICkgd2hpY2ggaXMgcHJvZHVjdCBvZiB0d28gcHJpbWVzCndoaWxlKChhW2ldKnRlbXApPD1MTVQpICAgICAvLyBwcm9jZXNzIGRvZXNub3Qgc3RvcHMsIHdlIHdpbGwgbXVsdGlwbHkgKCgoMTIqMykqMykqMy4uLi4gPD0xMDAwMDAwCnsgICAgICAgICAgICAgICAgICAgICAgICAgICAvLyBiY296IGFsbCB0aGVzZSByZXN1bHRzIGNhbiBiZSBkaXZpZGVkIGJ5IGFueSBudW1iZXIgb2YgdGltZXMgYnkgMyBhbmQgYXRsYXN0IGJlY29tZXMgNCB3aGljaCBpcyBwcm9kdWN0IG9mIHR3byBwcmltZXMKZmluYWxbYVtpXSp0ZW1wXT0xOyAgICAgICAgIC8vIHNhbWUgZm9yIGVhY2ggbnVtYmVyLgp0ZW1wPShsb25nKSh0ZW1wKmFbaV0pOwp9Cn0KfQp3aGlsZShxLS0pCnsKc2NhbmYoIiVsbGRcbiIsJnZhbCk7CmlmKHZhbD09MCkKcHJpbnRmKCJOT1xuIik7CmVsc2UKewppZihmaW5hbFt2YWxdKQpwcmludGYoIllFU1xuIik7CmVsc2UKcHJpbnRmKCJOT1xuIik7Cn0KfQpyZXR1cm4gMDsKfQp2b2lkIHNlaXZlKGJvb2wgYVtdLGludCBsbXQpCnsKbG9uZyBpbnQgaSxqLHRlbXAsdGVtcDE7CmZvcihpPTI7aTw9c3FydChsbXQpO2krKykKewppZihhW2ldKQp7CnRlbXA9KGxvbmcpaTsKZm9yKGo9Mjt0ZW1wKmo8PWxtdDtqKyspCnsKdGVtcDE9KGxvbmcpaTsKYVt0ZW1wMSpqXT0wOwp9Cn0KfQp9