fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct xor_128 {
  6. 	unsigned x,y,z,w;
  7. 	xor_128(): x(89165727), y(157892372), z(7777777), w(757328) {}
  8. 	unsigned next() {
  9. 		unsigned t=x^(x<<11);
  10. 		x=y;y=z;z=w;
  11. 		return w=w^(w>>19)^t^(t>>8);
  12. 	}
  13. 	unsigned next(unsigned k) {
  14. 		return next()%k;
  15. 	}
  16. }rng;
  17.  
  18. int n;
  19. int a[1<<14];
  20. vector <int> primes;
  21.  
  22. bool is_prime(int a) {
  23. 	if(a<2) return false;
  24. 	if(a==2) return true;
  25. 	int sq=sqrt(a),i;
  26. 	for(i=2;i<=sq;i++) if(a%i==0) return false;
  27. 	return true;
  28. }
  29.  
  30. bool check(int a) {
  31. 	int i;
  32. 	vector <int> v;
  33. 	for(i=0;i<(int)(primes.size());i++) {
  34. 		if((a|primes[i])==a) v.push_back(primes[i]);
  35. 	}
  36.  
  37. 	if(v.size()==0) return false;
  38.  
  39. 	for(i=1;i<=8000;i++) {
  40. 		int i1,i2,i3,i4;
  41. 		i1=rng.next(v.size());i2=rng.next(v.size());i3=rng.next(v.size());i4=rng.next(v.size());
  42. 		if((v[i1]|v[i2]|v[i3]|v[i4])==a) return true;
  43. 	}
  44.  
  45. 	return false;
  46. }
  47.  
  48. int main() {
  49. 	//ios_base::sync_with_stdio(false);
  50. 	//cin.tie(NULL);
  51. 	int i;
  52.  
  53. 	for(i=1;i<=8000;i++) if(is_prime(i)) primes.push_back(i);
  54.  
  55. 	scanf("%d", &n);
  56. 	for(i=1;i<=n;i++) {
  57. 		scanf("%d", &a[i]);
  58. 		if(check(a[i])) printf("YES\n");
  59. 		else printf("NO\n");
  60. 	}
  61.  
  62. 	return 0;
  63. }
  64.  
Success #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NPSnTu
language:
C++14 (gcc 8.3)
created:
9 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!