[BOJ][Python] 백준 15711번 - 환상의 짝꿍

문제 링크: https://www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

 

 

---

문제 풀이

A와 B의 범위가 너무 커서 에라토스테네스의 체를 이용을 망설였는데, 2백만 까지 돌려도 충분히 가능하다고 한다.

일단 A+B가 짝수인 경우와 홀수인 경우를 확인해야 한다. 소수는 기본적으로 2를 제외한 모든 소수는 홀수이다.

그리고 4 이상인 경우만 가능하다. 소수 중 가장 작은 수는 2인데, 2+2가 4이기 때문이다. (1은 소수가 아니다.)

 

1. 짝수인 경우

-  p + q(p, q는 홀수)인 경우이다. 골드바흐의 추측에 따르면 4 이상의 모든 짝수는 소수+소수가 가능하다.

다만, 모든 짝수인 경우는 정확히 알 수 없지만 문제에서 주어진 정수는 범위 내에 속해서 짝수인 경우는 모두 YES를 출력한다.

 

2. 홀수인 경우

- p(p는 홀수) + 2인 경우이다. 2는 소수이므로 p만 소수면 된다. 따라서 A+B가 s라 하면 s-2가 소수인지를 판단하면 된다. 이 경우에서도 두가지 경우가 존재한다.

첫 번째는 s-2가 $2\times {10}^6$보다 큰 경우이다. $2\times {10}^6$까지 소수를 구한 후 모든 소수로 나누었을 때 나눠지는게 없다면 소수이다.

A+B의 최댓값인 $4\times {10}^{12}$의 루트값이 $2\times {10}^6$이라 $2\times {10}^6$부터 $4\times {10}^{12}$까지 약수의 최댓값이 $2\times {10}^6$보다 큰 경우는 $4\times {10}^{12}$ 밖에 없을 것이다.

두 번째는 $2\times {10}^6$보다 작은 경우이다. $2\times {10}^6$보다 작은 소수를 구해놨기 때문에 바로 구할 수 있을 것이다. 집합으로 만들어 in을 이용했다. (시간복잡도는 O(1)이다.)

 

반복문이 많아 python은 시간 초과를 받아서 pypy로 제출했다.

 

 

코드

	from math import sqrt
	import sys
	input = sys.stdin.readline
	p = [1, 1] + [0] * 1999999
	for i in range(2, int(sqrt(2000000))+1):
	j = 2
	while i*j <= 2000000:
	p[i*j] = 1
	j += 1
	prime = set()
	for i in range(2, 2000001):
	if p[i] == 0:
	prime.add(i)
	for _ in range(int(input())):
	s = sum(map(int, input().split()))
	possi = True
	if s <= 3:
	print('NO')
	else:
	if s%2==0:
	print('YES')
	else:
	if s-2 > 2000000:
	for i in prime:
	if (s-2)%i==0:
	print('NO')
	possi = False
	break
	if possi:
	print('YES')
	else:
	if s-2 in prime:
	print('YES')
	else:
	print('NO')

view raw 15711.py hosted with ❤ by GitHub

 

 

참고 자료

https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

골드바흐의 추측 - 위키백과, 우리 모두의 백과사전