1990 소수인펠린드롬

소수이면서 펠린드롬인 숫자를 찾는 문제

시간 복잡도에 주의할 것

https://www.acmicpc.net/problem/1990

1. 문제

---

간단 설명

a부터 b사이의 숫자 중에서

펠린드롬이면서(거꾸로해도 같은 문자열), 소수인 숫자를 찾아 출력하기

2. 문제 분석

---

필요변수

시작 a, 끝 b

펠린드롬인지 판별할 IsPelidrome 함수

소수 판별할 IsPrime 함수

주의점

소수를 구할 때, 시간 복잡도에 주의한다

5 <= a, b <= 100,000,000 이므로

펠린드롬 계산은 얼마 걸리지 않아 패스

소수 계산에서 시간 복잡도가 상당함

쌩 노가다로 소수를 계산해버리면

O(N^2) 이므로 10^18. 1초를 넘어버림

에라토스테네스의 체를 이용하면 쉽게 구할 수 있다

알고리즘

1. a, b를 입력받고
2. 범위내 숫자 i가 펠린드롬인지 체크하고, 맞다면 소수 판별을 진행한다
    - if문에서 누가 먼저 오느냐에 따라 수행시간이 달라짐.
    - 펠린드롬을 먼저 체크하고 소수 판별을 진행할것인가, 아님 반대로?
    2-1. 펠린드롬 체크. 문자열을 반으로 쪼개서 끝부분부터 일치하는지 체크
    2-2. 소수 체크. 숫자를 2~sqrt(n)까지 숫자로 나눠본다. 나눠지면 소수 아님
    2-3. 두 조건을 만족했다면 숫자를 출력 
3. 다 출력했다면 -1 출력하고 종료

• 실제로 돌려보면 소수이면서, 펠린드롬인 숫자는 10,000,000 을 넘어선 나타나지 않는다 그래서 for문에서 이 이후의 숫자는 보지 않는걸로 처리해버림

https://www.acmicpc.net/board/view/1065

• 처음에는 에라토스테네스의 체를 1~N 까지 구해놓고 시작했으나, 시간초과남 (체를 채우는 과정에서 10^18번 수행)

왜 에라토스테네스 체를 sqrt(N)까지만 구하면 되는지 증명

3. 소스코드

---

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool prime[1000000001] = { 0 };

// 펠린드롬 판별 함수
bool IsPelindrome(int num) {
	string tmp = to_string(num);
	// 한자리는 무조건 펠린드롬임
	if (tmp.size() == 1) {
		return true;
	}

	// 두자리부터는 체크 들어감
	int mid = tmp.length() / 2;

	for (int i = 0; i < mid; i++) {
		if (tmp[i] != tmp[tmp.size() - 1 - i]) {
			return false;
		}
	}

	return true;
}

// 소수 판별 함수
bool IsPrime(int num) {
	if (num < 2) return false;

	for (int i = 2; i <= sqrt(num); i++) {
		if (num % i == 0) return false;
	}

	return true;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int a, b;
	cin >> a >> b;
	// 소수이고 펠린드롬이라면 출력
	for (int i = a; i <= 10000000; i++) {
		if (i > b) break;
		if (IsPelindrome(i) && IsPrime(i)) {
			cout << i << endl;
		}
		
	}
	cout << -1;

}

에라토스테네스 체는 sqrt(n)까지만 구하면 된다… 기억해두기!