[Algo Rhythm🕺💃]BOJ 6588 - 골드바흐의 추측

문제 분석

이 문제는 4보다 큰 어떤 짝수 $x (6 \le x \le 10^6)$가 두 홀수인 소수 $a, b (a \le b)$의 합으로 나타낼 수 있는지 판별하는 문제이다. 이때 주의할 점은 골드바흐의 추측은 $10^{18}$ 이하에서 참임이 확인되었기 때문에 두 홀수 소수의 합으로 나타내지 못 하는 경우는 생각하지 않아도 된다는 것이다.

 

문제 풀이

1. '소수 판별 알고리즘' 응용

주어진 $x$에 대하여 $a$의 가능한 최소값인 3부터 $x - a$인 $b$가 2보다 크지 않을 때까지 $a, b$ 모두 소수인지 판별한다.

만약 모두 소수라면 $x = a + b$를 출력한 뒤 반복문을 탈출하고 그렇지 않다면 $a$를 2씩 증가하고 위 과정을 반복한다. 이때 2씩 증가하는 이유는 짝수는 절대 소수가 될 수 없기 때문이다.

 

2. '에라토스테네스의 체' 응용

에라토스테니스의 체라는 소수를 구하는 알고리즘을 이용해 소수인 수와 아닌 수들을 구별한 배열을 만든다.

그리고나서 주어진 $x$에 대하여 $a$의 가능한 최소값인 3부터 $10^6$보다 작거나 같을 때까지 $a$와 $x - a$인 $b$가 모두 소수인지 판별한다. 이때 판별을 위해 앞서 만든 배열을 이용한다.

만약 모두 소수라면 $x = a + b$를 출력한 뒤 반복문을 탈출하고 그렇지 않다면 $a$를 2씩 증가하고 위 과정을 반복한다. 이때 2씩 증가하는 이유는 짝수는 절대 소수가 될 수 없기 때문이다.

 

복잡도 분석

테스트케이스로 주어지는 짝수 정수를 $x\ (6 \le x \le 10^6)$, 테스트케이스의 개수를 $y\ (1 \le y \le 10^5)$라고 할 때, 각 알고리즘의 시간 복잡도와 공간 복잡도는 다음과 같다.

 

1. '소수 판별 알고리즘' 응용

- 시간 복잡도 : $O(x\sqrt{x}y)$

 

1️⃣. 2️⃣번 과정을 테스트케이스의 개수인 y번 반복한다.

2️⃣. $a$를 찾기 위해 최악의 경우 3부터 $(x - 2)$번 2씩 증가하면서 3️⃣번 과정을 반복한다.

3️⃣. $a, b$ 모두 소수인지 판별한다.

 

1️⃣, 2️⃣, 3️⃣번 과정에서 소요되는 시간은 각각 $O(y), O(x), O(\sqrt{x})$ 이다.

따라서, 전체적인 시간복잡도는 $O(x\sqrt{x}y)$이다.

 

- 공간 복잡도 : O(1)

 

2. '에라토스테네스의 체' 응용

- 시간 복잡도 : $O(xlog(logx) + xy)$

 

소수인지 아닌지 구분하는 배열을 만들기 위해 에라토스테네스의 체를 사용하는데 이때 소요되는 시간은 O(xlog(logx))이다.

 

1️⃣. 2️⃣번 과정을 테스트케이스의 개수인 $y$번 반복한다.

2️⃣. $a$를 찾기 위해 최악의 경우 3부터 $10^6$까씩 2씩 증가한다.

 

1️⃣, 2️⃣번 과정에서 소요되는 시간은 각각 $O(y), O(x)$이다.

따라서, 전체적인 시간 복잡도는 $O(xlog(logx) + xy)$이다.

 

- 공간 복잡도 : O(x)

소수인지 아닌지 구분하는 배열의 크기는 x의 최대 크기인 10^6이다.

 

코드

1. '소수 판별 알고리즘' 응용

 

2. '에라토스테네스의 체' 응용

 

문제 출처

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

6588번: 골드바흐의 추측