김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1153 네 개의 소수 파이썬(Python)

문제 링크

상당히 씽크빅한 문제.
골드바흐의 추측을 사용해야 하는 문제다.
골드바흐 추측은 간단히 말해 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 추측이다.
추측인데도 문제를 푸는 데 쓸 수 있는 건, 문제 입력보다 훨씬 큰 범위에서 이미 참임이 증명되어 있기 때문이다.
어떤 수든지 소수 2 또는 3을 빼면 짝수로 만들 수 있다.
문제는 소수 네 개를 사용하므로 여기서 2를 한번 더 빼준다.
즉, 짝수에서는 4, 홀수에서는 5를 빼면 남은 수는 골드바흐 추측에 의해 두 개의 소수로 표현이 가능하다.
골드바흐의 추측을 만족하는 두 소수를 찾는 방법은 여러 가지가 있는데, 가장 나이브한 방법은 에라토스테네스의 체로 소수들을 거른 다음에 순회해서 소수들의 목록을 만드는 것이다.
이후에, 소수들의 목록을 순회하며 두 소수로 n을 나누는 경우를 찾으면 된다.
가장 작은 소수 2 네 개의 합인 8보다 작은 수는 절대 4개의 소수로 표현할 수 없으므로 -1을 출력해야 한다.

#!python

from sys import exit

n = int(input())

# 가장 작은 소수는 2이므로 2+2+2+2=8보다 작으면 무조건 안 된다
if n < 8:
    print(-1)
    exit()

# 에라토스테네스의 체
is_prime = [True for _ in range(n + 1)]
is_prime[0] = is_prime[1] = False

for i in range(2, int(n ** (1 / 2)) + 1):
    if is_prime[i]:
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False

# 체를 순회하면서 소수 리스트를 만들어준다
primes = []
for i in range(n + 1):
    if not is_prime[i]:
        continue
    primes.append(i)

# 홀수면 4개의 수 중 2개를 2, 3으로 고정
# 짝수면 4개의 수 중 2개를 2, 2로 고정
# 홀수 - 2 - 3 = 짝수
# 짝수 - 2 - 2 = 짝수
# 짝수면 골드바흐 추측에 의해 두 개의 소수의 합으로 나타낼 수 있다
if n % 2:
    n -= 5
    ans = 2, 3
else:
    n -= 4
    ans = 2, 2

# 소수를 순회하면서 n에서 그 소수를 뺀 게 소수면 답이다
for p in primes:
    if is_prime[n-p]:
        print(*(ans + (p, n-p)))
        break

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑