사용자 도구

사이트 도구


ps:problems:boj:1153

네 개의 소수

ps
링크https://www.acmicpc.net/problem/1153
출처BOJ
문제 번호1153
문제명네 개의 소수
레벨골드 4
분류

정수론

시간복잡도O(nloglogn)
인풋사이즈n<=1,000,000
사용한 언어Python
제출기록38840KB / 104ms
최고기록68ms
해결날짜2022/07/23

풀이

  • 보통 네개의 수의 합을 갖고 푸는 문제들 (예를 들면 수집합) 에서 주로 쓰이는 테크닉은 두 수의 합으로 만들어질수 있는 숫자들을 모두 구해놓고, 그것을 이용해서 다시 네 수의 합에 대해서 조사하는 것이다.
  • 그러나 이 문제는 그런 테크닉을 사용하기에도 범위가 너무 크다. 100만 이하의 소수의 갯수는 약 80000개인데, 그중에서 두개를 골라서 더해서 만들어지는 합의 갯수가 이미 감당 불가..
  • 대신 골드바흐 추측을 이용하면 문제가 간단해진다. 이에 따르면 모든 짝수는 2개의 소수의 합으로 나눌수 있다. 이제 간단히, N에서 소수 2개를 빼서 짝수로 만든 다음에, 그 짝수를 2개의 소수의 합으로 나누기만 하면 된다. 처음에 빼줄 소수 2개는 N이 홀수면 2와 3을, N이 짝수면 2와 2로 처리하면 간단하다.
  • 어떤 짝수 x를 2개의 소수의 합으로 나누는 것은 모든 소수 p에 대해서 x-p도 소수인지 확인하기만 하면 된다. 소수 목록을 구해서 set에 저장해두고 체크하면 된다. 소수 목록을 구하는 데에 O(nloglogn), 그렇게 얻은 O(n/logn)개의 소수에 대해서 x-p의 소수 여부를 체크하는 것은 O(1)이므로, 총 시간 복잡도는 O(nloglogn).

코드

"""Solution code for "BOJ 1153. 네 개의 소수".

- Problem link: https://www.acmicpc.net/problem/1153
- Solution link: http://www.teferi.net/ps/problems/boj/1153

Tags: [Number theory]
"""

from teflib import numtheory


def main():
    N = int(input())

    if N < 8:
        print('-1')
        return

    if N % 2:
        answer = [2, 3]
        target = N - 5
    else:
        answer = [2, 2]
        target = N - 4
    primes = set(numtheory.prime_list(N))
    p = next(x for x in primes if target - x in primes)

    print(*sorted([*answer, p, target - p]))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P Q P O​ H
 
ps/problems/boj/1153.txt · 마지막으로 수정됨: 2022/07/23 08:37 저자 teferi