[Python][백준 BOJ Silver Ⅱ] 9020. 골드바흐의 추측 : 에라토스테네스의 체, 범위 내에 존재하는 모든 소수

9020. 골드바흐의 추측

시간 제한 0.5초인 문제 '6588. 골드바흐의 추측'을 풀다가 진짜 10번 정도 시간 초과 발생해서 푸는  9020. 골드바흐의 추측.
그래 시간 제한 2초인 문제나 풀어보자 ^,,^

문제 풀기 전 유의할 것들!

시간 초과를 방지하려면 어떻게 해야할까?

테스트 케이스마다 해당 테스트 케이스보다 작은 소수들을 구해 prime[] 에 넣으면 시간과 공간이 많이 쓰인다.
따라서 테스트 케이스별로 소수를 구하는 것이 아니라, 소수를 구해놓고 모든 테스트 케이스에서 계속 사용하자.
각 테스트 케이스는 6 ≤ n ≤ 1000000인 짝수 정수이므로 범위 내의 소수를 미리 구해놓자.

에라토스테네스의 체

새롭게 알게된 소수 찾는 방법 !
에라토스테네스의 체란, 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법이다. 범위에서 소수가 아닌 수는 빼고 소수인 수만 남긴다.
임의의 자연수 n 미만의 소수를 전부 찾아내는데에 최적화된 알고리즘이며, 시간 복잡도는 O(NloglogN)으로 선형 시간에 가까울 정도로 매우 빠르다. 그러나 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.
https://www.youtube.com/watch?v=cswJ1h-How0 

 

내 풀이 - 오답

import math
import sys

# 0부터 10000까지의 수 중 소수인 수 리스트에 넣기
def eratosthenes_sieve(limit):
    is_prime = [True] * (limit + 1) # 0~10000까지 모든 수 소수인 것으로 일단 초기화
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            j = 2
            while i * j <= limit:
                is_prime[i * j] = False
                j += 1

    primes = [k for k in range(2, limit + 1) if is_prime[k]]
    return primes

# 변수에 할당하지 않고 매번 함수를 호출하면 호출할 때마다 새로운 소수 목록 생성됨 
primes = eratosthenes_sieve(10000)

t = int(sys.stdin.readline().rstrip())
n = [int(sys.stdin.readline()) for _ in range(t)]

# n 이하 소수 두개의 합이 n인 것?
for l in n:
    for m in primes:
        if m <= l:
            if (l - m) in primes:
                print(m, l-m)
                break

1. 문제에서 주어진 입력값의 범위는 4 ≤ n ≤ 10,000 이므로
   10000 이하의 소수를 primes라는 리스트에 미리 저장하고, 테스트 케이스가 들어올 때마다 해당 리스트를 사용한다.
2. primes에서 합이 n인 두 개의 요소를 찾는다. 

primes = eratosthenes_sieve() 함수를 primes라는 변수에 할당했다.
이렇게 하면 테스트 케이스가 입력될 때마다 새로운 소수 목록을 생성하지 않고, 만들어둔 소수 목록을 여러번 사용할 수 있다.

틀린 이유

그러나 위의 풀이의 경우 ' 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.' 라는 조건을 만족하지 않았다.

내 풀이 - 정답

import math
import sys

# 0부터 10000까지의 수 중 소수인 수 리스트에 넣기
def eratosthenes_sieve(limit):
    is_prime = [True] * (limit + 1) # 0~10000까지 모든 수 소수인 것으로 일단 초기화
    is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

    for i in range(2, int(math.sqrt(limit)) + 1):
        if is_prime[i]:
            j = 2
            while i * j <= limit:
                is_prime[i * j] = False
                j += 1

    primes = [k for k in range(2, limit + 1) if is_prime[k]]
    return primes
        
# 변수에 할당하지 않고 매번 함수를 호출하면 호출할 때마다 새로운 소수 목록 생성됨 
primes = eratosthenes_sieve(10000)

t = int(sys.stdin.readline().rstrip())
n = [int(sys.stdin.readline()) for _ in range(t)]

# n 이하 소수들 중 두 개의 합이 n인 것?
for l in n:
    prime1 = prime2 = l // 2
    while 1:
        if prime1 in primes and prime2 in primes:
            print(prime1, prime2)
            break
        else:
            prime1 -= 1
            prime2 += 1

입출력 예시를 보면 prime1과 prime2는 같은 값이여도 되기 때문에, prime1 = prime2 = l // 2 를 초기값으로 두고, 두 값이 위에서 구한 primes(10000 이하의 소수)에 있을 때까지 prime1은 1씩 작게, prime2는 1씩 크게 만들어준다.
prime1은 소수이므로 2 이상의 수일 것이기 때문에 while문의 조건은 그냥 1로 설정했다!
 
아래 필기와 같은 흐름 ~.~

 

1) -> 2) -> 3) -> 4) 순으로 두 수의 차이가 적다.

 

---

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

9020번: 골드바흐의 추측

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

6588번: 골드바흐의 추측