Ideone.com

download

copy

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
typedef unsigned long long ull;
const int bits = 10;
// if all numbers are less than 2^k, set bits = 64-k
const ull po = 1 << bits;
 
ull mod_mul(ull a, ull b, ull &c) {
	ull x = a * (b & (po - 1)) % c;
	while ((b >>= bits) > 0) {
		a = (a << bits) % c;
		x += (a * (b & (po - 1))) % c;
	}
	return x % c;
}
 
ull mod_pow(ull a, ull b, ull mod) {
	if (b == 0) return 1;
	ull res = mod_pow(a, b / 2, mod);
	res = mod_mul(res, res, mod);
	if (b & 1) return mod_mul(res, a, mod);
	return res;
}
 
bool prime(ull p) {
	if (p == 2) return true;
	if (p == 1 || p % 2 == 0) return false;
	ull s = p - 1;
	while (s % 2 == 0) s /= 2;
	rep(i,0,15) {
		ull a = rand() % (p - 1) + 1, tmp = s;
		ull mod = mod_pow(a, tmp, p);
		while (tmp != p - 1 && mod != 1 && mod != p - 1) {
			mod = mod_mul(mod, mod, p);
			tmp *= 2;
		}
		if (mod != p - 1 && tmp % 2 == 0) return false;
	}
	return true;
}
 
const int N = 1e7;
const int N2 = 10;
vector<bool> isPrime(N, true);
vector<int> primes;
int smallPrimes[N2];
 
void pre() {
	isPrime[0] = isPrime[1] = false;
	for(int i = 4; i < N; i += 2) {
		isPrime[i] = false;
	}
	for(int i = 3; i*i < N; i += 2) {
		if(isPrime[i]) {
			primes.push_back(i);
			for(int j = 2*i; j < N; j += i) {
				isPrime[j] = false;
			}
		}
	}
	for(int i = 0; i < N2; i++) {
		smallPrimes[i] = primes[i];
	}
}
 
bool is_prime(int n) {
	if(n < N) {
		return isPrime[n];
	}
	return prime(n);
	/*
	for(int i : primes) {
		if(i*i > n) {
			return true;
		}
		if(n%i == 0) {
			return false;
		}
	}
	*/
}
 
bool is_prime2(int n) {
	for(int i : smallPrimes) {
		if(n != i && n%i == 0) {
			return false;
		}
	}
	return true;
}
 
bool isPop(int x) {
	string a = to_string(x);
	int n = a.length();
	if(!is_prime(x)) {
		return false;
	}
	vector<int> dp(n);
	for(int j = 0; j < n-1; j++) {
		for(int k = j; k >= 0; k--) {
			if(a[k] == '0' || a[j+1] == '0') {
				continue;
			}
			int i1 = stoi(a.substr(k, j+1));
			if(!is_prime2(i1)) {
				continue;
			}
			bool b11 = is_prime(i1);
			if(!b11) {
				continue;
			}
			if(k >= 1) {
				dp[j] += dp[k-1];
			} else {
				dp[j]++;
			}
			int i2 = stoi(a.substr(j+1, n));
			if(!is_prime2(i2)) {
				continue;
			}
			bool b22 = is_prime(i2);
			if(b22) {
				if(k >= 1) {
					if(dp[k-1] > 0) {
						return true;
					}
				} else {
					return true;
				}
			}
		}
	}
	return false;
}
 
int main() {
	pre();
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		//n = 782690999;
		while(true) {
			if(is_prime2(n) && isPop(n)) {
				printf("%d\n", n);
				break;
			}
			n++;
		}
	}
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHJlcChpLCBmcm9tLCB0bykgZm9yIChpbnQgaSA9IGZyb207IGkgPCAodG8pOyArK2kpCiNkZWZpbmUgdHJhdihhLCB4KSBmb3IgKGF1dG8mIGEgOiB4KQojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSBzeih4KSAoaW50KSh4KS5zaXplKCkKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcGlpOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwoKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwpjb25zdCBpbnQgYml0cyA9IDEwOwovLyBpZiBhbGwgbnVtYmVycyBhcmUgbGVzcyB0aGFuIDJeaywgc2V0IGJpdHMgPSA2NC1rCmNvbnN0IHVsbCBwbyA9IDEgPDwgYml0czsKCnVsbCBtb2RfbXVsKHVsbCBhLCB1bGwgYiwgdWxsICZjKSB7Cgl1bGwgeCA9IGEgKiAoYiAmIChwbyAtIDEpKSAlIGM7Cgl3aGlsZSAoKGIgPj49IGJpdHMpID4gMCkgewoJCWEgPSAoYSA8PCBiaXRzKSAlIGM7CgkJeCArPSAoYSAqIChiICYgKHBvIC0gMSkpKSAlIGM7Cgl9CglyZXR1cm4geCAlIGM7Cn0KCnVsbCBtb2RfcG93KHVsbCBhLCB1bGwgYiwgdWxsIG1vZCkgewoJaWYgKGIgPT0gMCkgcmV0dXJuIDE7Cgl1bGwgcmVzID0gbW9kX3BvdyhhLCBiIC8gMiwgbW9kKTsKCXJlcyA9IG1vZF9tdWwocmVzLCByZXMsIG1vZCk7CglpZiAoYiAmIDEpIHJldHVybiBtb2RfbXVsKHJlcywgYSwgbW9kKTsKCXJldHVybiByZXM7Cn0KCmJvb2wgcHJpbWUodWxsIHApIHsKCWlmIChwID09IDIpIHJldHVybiB0cnVlOwoJaWYgKHAgPT0gMSB8fCBwICUgMiA9PSAwKSByZXR1cm4gZmFsc2U7Cgl1bGwgcyA9IHAgLSAxOwoJd2hpbGUgKHMgJSAyID09IDApIHMgLz0gMjsKCXJlcChpLDAsMTUpIHsKCQl1bGwgYSA9IHJhbmQoKSAlIChwIC0gMSkgKyAxLCB0bXAgPSBzOwoJCXVsbCBtb2QgPSBtb2RfcG93KGEsIHRtcCwgcCk7CgkJd2hpbGUgKHRtcCAhPSBwIC0gMSAmJiBtb2QgIT0gMSAmJiBtb2QgIT0gcCAtIDEpIHsKCQkJbW9kID0gbW9kX211bChtb2QsIG1vZCwgcCk7CgkJCXRtcCAqPSAyOwoJCX0KCQlpZiAobW9kICE9IHAgLSAxICYmIHRtcCAlIDIgPT0gMCkgcmV0dXJuIGZhbHNlOwoJfQoJcmV0dXJuIHRydWU7Cn0KCmNvbnN0IGludCBOID0gMWU3Owpjb25zdCBpbnQgTjIgPSAxMDsKdmVjdG9yPGJvb2w+IGlzUHJpbWUoTiwgdHJ1ZSk7CnZlY3RvcjxpbnQ+IHByaW1lczsKaW50IHNtYWxsUHJpbWVzW04yXTsKCnZvaWQgcHJlKCkgewoJaXNQcmltZVswXSA9IGlzUHJpbWVbMV0gPSBmYWxzZTsKCWZvcihpbnQgaSA9IDQ7IGkgPCBOOyBpICs9IDIpIHsKCQlpc1ByaW1lW2ldID0gZmFsc2U7Cgl9Cglmb3IoaW50IGkgPSAzOyBpKmkgPCBOOyBpICs9IDIpIHsKCQlpZihpc1ByaW1lW2ldKSB7CgkJCXByaW1lcy5wdXNoX2JhY2soaSk7CgkJCWZvcihpbnQgaiA9IDIqaTsgaiA8IE47IGogKz0gaSkgewoJCQkJaXNQcmltZVtqXSA9IGZhbHNlOwoJCQl9CgkJfQoJfQoJZm9yKGludCBpID0gMDsgaSA8IE4yOyBpKyspIHsKCQlzbWFsbFByaW1lc1tpXSA9IHByaW1lc1tpXTsKCX0KfQoKYm9vbCBpc19wcmltZShpbnQgbikgewoJaWYobiA8IE4pIHsKCQlyZXR1cm4gaXNQcmltZVtuXTsKCX0KCXJldHVybiBwcmltZShuKTsKCS8qCglmb3IoaW50IGkgOiBwcmltZXMpIHsKCQlpZihpKmkgPiBuKSB7CgkJCXJldHVybiB0cnVlOwoJCX0KCQlpZihuJWkgPT0gMCkgewoJCQlyZXR1cm4gZmFsc2U7CgkJfQoJfQoJKi8KfQoKYm9vbCBpc19wcmltZTIoaW50IG4pIHsKCWZvcihpbnQgaSA6IHNtYWxsUHJpbWVzKSB7CgkJaWYobiAhPSBpICYmIG4laSA9PSAwKSB7CgkJCXJldHVybiBmYWxzZTsKCQl9Cgl9CglyZXR1cm4gdHJ1ZTsKfQoKYm9vbCBpc1BvcChpbnQgeCkgewoJc3RyaW5nIGEgPSB0b19zdHJpbmcoeCk7CglpbnQgbiA9IGEubGVuZ3RoKCk7CglpZighaXNfcHJpbWUoeCkpIHsKCQlyZXR1cm4gZmFsc2U7Cgl9Cgl2ZWN0b3I8aW50PiBkcChuKTsKCWZvcihpbnQgaiA9IDA7IGogPCBuLTE7IGorKykgewoJCWZvcihpbnQgayA9IGo7IGsgPj0gMDsgay0tKSB7CgkJCWlmKGFba10gPT0gJzAnIHx8IGFbaisxXSA9PSAnMCcpIHsKCQkJCWNvbnRpbnVlOwoJCQl9CgkJCWludCBpMSA9IHN0b2koYS5zdWJzdHIoaywgaisxKSk7CgkJCWlmKCFpc19wcmltZTIoaTEpKSB7CgkJCQljb250aW51ZTsKCQkJfQoJCQlib29sIGIxMSA9IGlzX3ByaW1lKGkxKTsKCQkJaWYoIWIxMSkgewoJCQkJY29udGludWU7CgkJCX0KCQkJaWYoayA+PSAxKSB7CgkJCQlkcFtqXSArPSBkcFtrLTFdOwoJCQl9IGVsc2UgewoJCQkJZHBbal0rKzsKCQkJfQoJCQlpbnQgaTIgPSBzdG9pKGEuc3Vic3RyKGorMSwgbikpOwoJCQlpZighaXNfcHJpbWUyKGkyKSkgewoJCQkJY29udGludWU7CgkJCX0KCQkJYm9vbCBiMjIgPSBpc19wcmltZShpMik7CgkJCWlmKGIyMikgewoJCQkJaWYoayA+PSAxKSB7CgkJCQkJaWYoZHBbay0xXSA+IDApIHsKCQkJCQkJcmV0dXJuIHRydWU7CgkJCQkJfQoJCQkJfSBlbHNlIHsKCQkJCQlyZXR1cm4gdHJ1ZTsKCQkJCX0KCQkJfQoJCX0KCX0KCXJldHVybiBmYWxzZTsKfQogCmludCBtYWluKCkgewoJcHJlKCk7CglpbnQgdDsKCXNjYW5mKCIlZCIsICZ0KTsKCXdoaWxlKHQtLSkgewoJCWludCBuOwoJCXNjYW5mKCIlZCIsICZuKTsKCQkvL24gPSA3ODI2OTA5OTk7CgkJd2hpbGUodHJ1ZSkgewoJCQlpZihpc19wcmltZTIobikgJiYgaXNQb3AobikpIHsKCQkJCXByaW50ZigiJWRcbiIsIG4pOwoJCQkJYnJlYWs7CgkJCX0KCQkJbisrOwoJCX0KCX0KfQ==

Runtime error #stdin #stdout 0.06s 4360KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/USdjT0

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language