[ 2023-03-16 🌺 TIL ]

백준 17103번

콜드바흐의 파티션의 갯수를 구하는 문제

짝수 값 a가 들어오면 b + c = a가 되는 값을 구하는 문재 (여기서 b와 c는 둘 다 소수여야 한다.)

b와 c의 값이 순서만 다른 값은 쳐주지 않는다 ex) 3+7 = 10, 7+3 = 10 이럴 경우 한개로 카운트된다.

처음에는 아래와 같이 코드를 구성하였는데 시간초과..가 발생하였다.
코드는 느리지만 맞는 답은 출력하는 코드입니다.

import sys

input = sys.stdin.readline

t = int(input())


def sosu(n):
    sqrt = int(n ** (0.5)) + 1
    count = 0
    for i in range(2, sqrt):
        if n % i == 0:
            return False
    return True


for _ in range(t):
    n = int(input())
    if n == 2:
        print(0)
        continue
    half = n//2
    count = 0
    for i in range(2, half+1):
        if sosu(i) and sosu(n-i):
            count += 1
    print(count)

이를 해결하기 위하여 구글링을 하였고 에라토스테네스의 체를 사용하여 문제를 푸는 방법을 알게되었습니다.

에라토스테네스의 체
소수를 구하면 그에 배수 되는 수들을 제거하여 나머지 수들에서 소수들을 구할 수 있다.

import sys

input = sys.stdin.readline

t = int(input())
t_li = []
max_t = -1

for _ in range(t):
    n = int(input())
    t_li.append(n)
    if max_t < n:
        max_t = n  # 입력값중에 가장 큰 수

sosu_li = [True] * (max_t + 1)  # 0 ~ 최댓값까지의 수와 인덱스 같은 배열 선언
sosu_li[1] = False  # 1일 걍우 모든 경우의 약수이니 False 넣음


def sosu(n):
    global sosu_li
    sqrt = int(n ** (0.5)) + 1
    count = 0
    for i in range(2, sqrt):  # i가 i의 배수인 것을 찾아 False로 변경
        if sosu_li[i]:
            for j in range(i+i, max_t+1, i):
                sosu_li[j] = False
            # 소수안 값은 True인 것으로 남는다.
sosu(max_t)

for n in t_li:
    count = 0
    for i in range(2, (n//2) + 1): # 순서만 다른 값들은 몰라도 되기에 반까지만 구하면된다.
        if sosu_li[i] and sosu_li[n-i]: 
            count += 1
    print(count)