[Python] 백준 : 골드바흐 파티션 17103, 소수 구하기, 에라토스테네스의 체

 

 

📝 문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

🫠 나의 풀이 (시간 초과)

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

T = int(input())

def prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0: return False
    return True

for _ in range(T):
    N = int(input())
    cnt = 0

    for i in range(2, N // 2 + 1):
        if prime(i) and prime(N - i):
            cnt += 1

    print(cnt)

 

🧞‍♂️ 다른 사람의 풀이

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

T = int(input())
MAX = 1000000
is_prime = [1] * (MAX + 1)
is_prime[0] = is_prime[1] = 0

# 15: i의 배수는 소수가 아니므로, is_prime[j] => 0 으로 설정.
# 반복문은 i * i부터 시작 => 그 이전의 배수들은 이미 더 작은 소수들에 의해 처리되었기 때문.
# 예로, 2의 배수인 4, 6, 8, ..., 그리고 3의 배수인 6, 9, 12, ... 등은 이미 앞에서 처리됨.
# i = 5일 때 25보다 작은 배수인 10, 15, 20 등은 이미 2나 3에서 처리된 상태.
for i in range(2, int(MAX ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, MAX + 1, i):
            is_prime[j] = 0

for _ in range(T):
    N = int(input())
    cnt = 0

    for i in range(2, N // 2 + 1):
        if is_prime[i] and is_prime[N - i]:
            cnt += 1

    print(cnt)

 

 

 

🔗 https://www.acmicpc.net/problem/17103