fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, from, to) for (int i = from; i < (to); ++i)
  5. #define trav(a, x) for (auto& a : x)
  6. #define all(x) x.begin(), x.end()
  7. #define sz(x) (int)(x).size()
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  10. typedef vector<int> vi;
  11.  
  12. typedef unsigned long long ull;
  13. const int bits = 10;
  14. // if all numbers are less than 2^k, set bits = 64-k
  15. const ull po = 1 << bits;
  16.  
  17. ull mod_mul(ull a, ull b, ull &c) {
  18. 	ull x = a * (b & (po - 1)) % c;
  19. 	while ((b >>= bits) > 0) {
  20. 		a = (a << bits) % c;
  21. 		x += (a * (b & (po - 1))) % c;
  22. 	}
  23. 	return x % c;
  24. }
  25.  
  26. ull mod_pow(ull a, ull b, ull mod) {
  27. 	if (b == 0) return 1;
  28. 	ull res = mod_pow(a, b / 2, mod);
  29. 	res = mod_mul(res, res, mod);
  30. 	if (b & 1) return mod_mul(res, a, mod);
  31. 	return res;
  32. }
  33.  
  34. bool prime(ull p) {
  35. 	if (p == 2) return true;
  36. 	if (p == 1 || p % 2 == 0) return false;
  37. 	ull s = p - 1;
  38. 	while (s % 2 == 0) s /= 2;
  39. 	rep(i,0,15) {
  40. 		ull a = rand() % (p - 1) + 1, tmp = s;
  41. 		ull mod = mod_pow(a, tmp, p);
  42. 		while (tmp != p - 1 && mod != 1 && mod != p - 1) {
  43. 			mod = mod_mul(mod, mod, p);
  44. 			tmp *= 2;
  45. 		}
  46. 		if (mod != p - 1 && tmp % 2 == 0) return false;
  47. 	}
  48. 	return true;
  49. }
  50.  
  51. const int N = 2e7;
  52. const int N2 = 7;
  53. bool isPrime[N];
  54. vector<int> primes;
  55. int smallPrimes[N2];
  56.  
  57. void pre() {
  58. 	fill(isPrime, isPrime+N, true);
  59. 	isPrime[0] = isPrime[1] = false;
  60. 	for(int i = 2; i < N; i++) {
  61. 		if(isPrime[i]) {
  62. 			primes.push_back(i);
  63. 			for(int j = 2*i; j < N; j += i) {
  64. 				isPrime[j] = false;
  65. 			}
  66. 		}
  67. 	}
  68. 	for(int i = 0; i < N2; i++) {
  69. 		smallPrimes[i] = primes[i];
  70. 	}
  71. }
  72.  
  73. bool is_prime(int n) {
  74. 	if(n < N) {
  75. 		return isPrime[n];
  76. 	}
  77. 	return prime(n);
  78. 	/*
  79. 	for(int i : primes) {
  80. 		if(i*i > n) {
  81. 			return true;
  82. 		}
  83. 		if(n%i == 0) {
  84. 			return false;
  85. 		}
  86. 	}
  87. 	*/
  88. }
  89.  
  90. bool is_prime2(int n) {
  91. 	for(int i : smallPrimes) {
  92. 		if(n%i == 0) {
  93. 			return false;
  94. 		}
  95. 	}
  96. 	return true;
  97. }
  98.  
  99. bool isPop(int x) {
  100. 	string a = to_string(x);
  101. 	int n = a.length();
  102. 	if(!is_prime(x)) {
  103. 		return false;
  104. 	}
  105. 	vector<int> dp(n);
  106. 	for(int j = 0; j < n-1; j++) {
  107. 		for(int k = j; k >= 0; k--) {
  108. 			if(a[k] == '0' || a[j+1] == '0') {
  109. 				continue;
  110. 			}
  111. 			int i1 = stoi(a.substr(k, j+1));
  112. 			if(!is_prime2(i1)) {
  113. 				continue;
  114. 			}
  115. 			bool b11 = is_prime(i1);
  116. 			if(!b11) {
  117. 				continue;
  118. 			}
  119. 			if(k >= 1) {
  120. 				dp[j] += dp[k-1];
  121. 			} else {
  122. 				dp[j]++;
  123. 			}
  124. 			int i2 = stoi(a.substr(j+1, n));
  125. 			if(!is_prime2(i2)) {
  126. 				continue;
  127. 			}
  128. 			bool b22 = is_prime(i2);
  129. 			if(b22) {
  130. 				if(k >= 1) {
  131. 					if(dp[k-1] > 0) {
  132. 						return true;
  133. 					}
  134. 				} else {
  135. 					return true;
  136. 				}
  137. 			}
  138. 		}
  139. 	}
  140. 	return false;
  141. }
  142.  
  143. int main() {
  144. 	pre();
  145. 	int t;
  146. 	scanf("%d", &t);
  147. 	map<int, int> mp;
  148. 	while(t--) {
  149. 		int n;
  150. 		scanf("%d", &n);
  151. 		vector<int> v;
  152. 		while(true) {
  153. 			if(mp.count(n) > 0) {
  154. 				printf("%d\n", mp[n]);
  155. 				break;
  156. 			}
  157. 			v.push_back(n);
  158. 			if(is_prime2(n) && isPop(n)) {
  159. 				printf("%d\n", n);
  160. 				break;
  161. 			}
  162. 			n++;
  163. 		}
  164. 		for(int i : v) {
  165. 			mp[i] = n;
  166. 		}
  167. 	}
  168. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:150:14: error: invalid operands of types ‘const char [3]’ and ‘int’ to binary ‘operator&’
   scanf("%d" &n);
         ~~~~~^~
stdout
copy 
Standard output is empty
https://ideone.com/JGdnE4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!