fork download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<stdbool.h>
  4. #define MAX 1000010
  5. #define LMT 1000000
  6. #define END 100000000 //9
  7. bool a[MAX];
  8. int count;
  9. void seive(bool a[],int lmt);
  10. int gen[10000000];
  11. bool final[END];
  12. int main(void)
  13. {
  14. long long int i,j,n,q,temp,length,val;
  15. for(i=2;i<=LMT;i++)
  16. a[i]=1;
  17. seive(a,LMT);
  18. for(i=2;i<=LMT;i++)
  19. if(a[i])
  20. count+=1;
  21. int prime[count];
  22. length=0;
  23. for(i=0;i<=LMT;i++)
  24. {
  25. if(a[i])
  26. {
  27. prime[length]=i;
  28. // printf("%d\n",prime[length]);
  29. length+=1;
  30. // printf("L= %d\n",length);
  31. }
  32.  
  33. }
  34. // printf("last prime = %d secondlast= %d \n",prime[length-1],prime[length-2]);
  35. long long int genlen=0;
  36.  
  37. int flag=0;
  38. for(i=0;i<length;i++)
  39. {
  40. temp=(long)(prime[i]);
  41. for(j=i;j<length;j++)
  42. {
  43. if((temp*prime[j])>LMT && i==j)
  44. {
  45. flag=1;
  46. break;
  47. }
  48. if((temp*prime[j])>LMT)
  49. {
  50. break;
  51. }
  52.  
  53. gen[genlen]=temp*prime[j];
  54. genlen+=1;
  55. }
  56. if(flag)
  57. break;
  58. }
  59. // printf("%lld %lld\n",length,genlen);
  60.  
  61. for(i=0;i<genlen;i++)
  62. final[gen[i]]=1;
  63. scanf("%lld %lld",&n,&q);
  64. int a[n];
  65. for(i=0;i<n;i++)
  66. scanf("%d",&a[i]);
  67. for(i=0;i<n;i++)
  68. {
  69.  if(a[i]==1 || a[i]==0)
  70.  continue;
  71. for(j=0;j<genlen;j++)
  72. {
  73. temp=(long)(gen[j]);
  74. if((temp*a[i])>LMT)
  75. continue;
  76. while((a[i]*temp)<=LMT)
  77. {
  78. final[a[i]*temp]=1;
  79. temp=(long)(temp*a[i]);
  80. }
  81. }
  82. }
  83. while(q--)
  84. {
  85. scanf("%lld\n",&val);
  86. if(val==0)
  87. printf("NO\n");
  88. else
  89. {
  90. if(final[val])
  91. printf("YES\n");
  92. else
  93. printf("NO\n");
  94. }
  95. }
  96. return 0;
  97. }
  98. void seive(bool a[],int lmt)
  99. {
  100. long int i,j,temp,temp1;
  101. for(i=2;i<=sqrt(lmt);i++)
  102. {
  103. if(a[i])
  104. {
  105. temp=(long)i;
  106. for(j=2;temp*j<=lmt;j++)
  107. {
  108. temp1=(long)i;
  109. a[temp1*j]=0;
  110. }
  111. }
  112. }
  113. }
Runtime error #stdin #stdout 0s 147328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R25V7u
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!