Boj 1990) 소수인팰린드롬

문제

백준 1990

설명

주어진 수의 범위가 1e9 라서 잘못하면 TLE 가 날 수 있다. 특히 소수 판정을 1~1e9 에 대해 수행하면 안된다. 코드가 조금만 복잡해도 1초가 넘는 범위이기 때문에 어떤 효율적인 알고리즘이라도 TLE 를 벗어날 수 없다.

대신 팰리드롬인 수는 좌우대칭이므로 범위의 자리수가 절반이다.

• 1~9999 까지 순서대로 선택한 수를 a 라고 하고,
• 수를 거꾸로 하는 함수를 inv() 라고 하면,
• 팰린드롬인 수를 정규식으로 표현하면 ^a[0~9]?inv(a)$ 이기 때문이다.

그래서 이에 대해서만 소수판정을 해주면 주어진 시간 내에 계산할 수 있다.

짝수 소수인팰린드롬

이때 성능 상에는 큰 영향이 없지만 코드를 간략하게 해주는 성질이 있다. 바로 주어진 범위에서 소수이면서 팰린드롬이기 위해서는 자리수가 홀수여야 한다는 사실이다(11 제외). 이에 대한 증명은 간단하다.

a00a = 1001 * a = 11 * 7 * 13 * a
bb0 = 110 * b = 11 * 10 * b
abba = a00a + bb0 = 11 * some

위는 4자리에 대해서 수행하였지만 비슷한 작업을 6자리, 8자리에 대해서도 간단히 수행할 수 있다.

이를 제외해도 시간복잡도 상으로는 차이가 없지만 재밌는 성질이라 여기에 메모한다.

시간 복잡도

O(\(\mathrm{100000}\))

코드

int erasto[40000];
vector<int> primes, ans;

inline bool IsPrime(int i) {
	for (auto p : primes) if (i != p && i % p == 0) return false;
	return true;
}

int main()
{
	erasto[0] = erasto[1] = 1;
	for (int i = 2; i < 40000; i++)
		if (!erasto[i])
			for (int j = i + i; j < 40000; j += i)
				erasto[j] = true;

	for (int i = 2; i < 40000; i++)
		if (!erasto[i])
			primes.push_back(i);

	for (auto p : primes)
	{
		if (p > 12) break;
		ans.push_back(p);
	}

	char in[20];
	for (int th = 10, len = 1; th < 100000; th*=10, len++)
	{
		for (int i = th/10; i < th; i++)
		{
			sprintf(in, "%d", i);
			for (int j = strlen(in); j < len; j++) in[j] = '0';
			for (int j = 0; j < len; j++) in[2 * len - j] = in[j];
			in[len * 2+1] = '\0';
			for (int k = 0; k < 10; k++)
			{
				in[len] = k + '0';
				int cur = stoi(in);
				if (IsPrime(cur)) ans.push_back(cur);
			}
		}
	}

	int a, b; cin >> a >> b;
	sort(ans.begin(), ans.end());

	auto begin = lower_bound(ans.begin(), ans.end(), a);
	auto end = lower_bound(ans.begin(), ans.end(), b + 1);
	for (auto iter = begin; iter != end; iter++)
		cout << *iter << '\n';
	cout << -1;
}