[C++] 백준 1990번: 소수인팰린드롬

문제 링크

1990번: 소수인팰린드롬

문제 요약

a부터 b까지의, 소수이면서 팰린드롬인 수를 모두 출력해야 한다.

접근 방법

a부터 b까지의 수를 하나하나씩 팰린드롬인지 검사하고, 소수인지 검사하는 식으로 접근하면 바로 TLE를 받습니다. B의 최댓값이 1억임에도 불구하고 시간은 1초만 주어지기 때문입니다.

그래서 저도 TLE를 몇번 받고, 제가 짠 코드에 5 100000000을 입력으로 넣어보았습니다. 그러자 9989899까지는 빠르게 출력되었습니다. 하지만 그 이후로는 한참동안 아무것도 출력되지 않다가 -1이 출력되었습니다. 즉, 검사를 $MIN(b, 9989899)$까지만 해주면 된다는 것이었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int a, b;
	cin >> a >> b;

	for (int i = a; i <= min(b, 9989899); i++)
	{
		string str = to_string(i);

		bool flag = false;
		for (int j = 0; j < str.size() / 2; j++)
		{
			if (str[j] != str[str.size() - j - 1])
			{
				flag = true;
				break;
			}
		}

		if (flag)
			continue;

		for (int j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = true;
				break;
			}
		}

		if (!flag)
			cout << i << '\n';
	}

	cout << -1 << '\n';
	return 0;
}