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;              // total number of prime numbers till 1000000
  21. int prime[count];       // array of that size and storing all these prime numbers in array prime[]
  22. length=0;
  23. for(i=0;i<=LMT;i++)
  24. {
  25. if(a[i])
  26. {
  27. prime[length]=i;
  28. length+=1;
  29. }
  30. }
  31. long long int genlen=0;        
  32. int flag=0;
  33. for(i=0;i<length;i++)        // now making gen[] to store all possible 2 multiples of these prime numbers stored
  34. {							// in prime[] ,if only product of these two primes is <=1000000
  35. temp=(long)(prime[i]);
  36. for(j=i;j<length;j++)
  37. {
  38. if((temp*prime[j])>LMT && i==j)
  39. {
  40. flag=1;
  41. break;
  42. }
  43. if((temp*prime[j])>LMT)
  44. {
  45. break;
  46. }
  47. gen[genlen]=temp*prime[j];
  48. genlen+=1;
  49. }
  50. if(flag)
  51. break;
  52. }
  53. for(i=0;i<genlen;i++)    // now marking all these two times multiples of each primes as 1 bcoz , all these result
  54. final[gen[i]]=1;         // can directly decompose into two prime multiples
  55. scanf("%lld %lld",&n,&q);
  56. int a[n];
  57. for(i=0;i<n;i++)
  58. scanf("%d",&a[i]);
  59. for(i=0;i<n;i++)            // now other set of numbers which can be decompose into two prime multiples will be
  60. {                           // product of given array number into one of these generated number(gen[i]),and all its
  61.                             // multiples ,till its less than 1000000. follow these for each given number with each generated array number(gen[i])
  62. for(j=0;j<genlen;j++)
  63. {                            // for e.g = given array = 3 2 6
  64. temp=(long)(gen[j]);         // eg generated prime= 4 5 9 15
  65. if((temp*gen[j])>LMT)        // now mark product of given array(a[i]) and generated array(gen[i])=(3*4=12)
  66. break;                       // bcoz 12 can be decompose to 4 (dividing by 3 ) which is product of two primes
  67. while((a[i]*temp)<=LMT)     // process doesnot stops, we will multiply (((12*3)*3)*3.... <=1000000
  68. {                           // bcoz all these results can be divided by any number of times by 3 and atlast becomes 4 which is product of two primes
  69. final[a[i]*temp]=1;         // same for each number.
  70. temp=(long)(temp*a[i]);
  71. }
  72. }
  73. }
  74. while(q--)
  75. {
  76. scanf("%lld\n",&val);
  77. if(val==0)
  78. printf("NO\n");
  79. else
  80. {
  81. if(final[val])
  82. printf("YES\n");
  83. else
  84. printf("NO\n");
  85. }
  86. }
  87. return 0;
  88. }
  89. void seive(bool a[],int lmt)
  90. {
  91. long int i,j,temp,temp1;
  92. for(i=2;i<=sqrt(lmt);i++)
  93. {
  94. if(a[i])
  95. {
  96. temp=(long)i;
  97. for(j=2;temp*j<=lmt;j++)
  98. {
  99. temp1=(long)i;
  100. a[temp1*j]=0;
  101. }
  102. }
  103. }
  104. }
Runtime error #stdin #stdout 0.01s 148224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/foMTE3
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!