진짜진짜진짜 짜증났던 문제!!!
엄청 틀리면서 겨우겨우 풀었다 휴ㅜㅜ
문제 내용 자체는 크게 어렵지 않았다.
1. 소수를 구하고,
2. 주어진 짝수 정수 N에서 N=a+b를 만족하는 a,b를 구하라
이 두 가지가 전부인 문제다.
소수를 구하는 방법에는 여러가지가 있지만, 이번 문제처럼 주어진 범위가 클 때 가장 많이 사용하는 방법이 있다. 바로 '에레토스테네스의 체'다.
에라토스테네스의 체에 대해서는 여기에 대해에 따로 작성해두었다.
import math, sys
input = sys.stdin.readline
number = 1000000
prime = [True for i in range(number+1)]
prime[1] = 0
for i in range (2, int(math.sqrt(number))+1):
if(prime[i] == True):
j = 2
while i*j <= number:
prime[i*j] = False
j += 1
while(True):
hasGold = False
n = int(input().rstrip())
if n < 6 or n > number or n == 0:
break
for i in range(3, number+1, 2):
if(prime[i] and prime[n - i]):
hasGold = True
print(n, "=", i, "+", n-i)
break
if not hasGold:
print("Goldbach's conjecture is wrong.")
break
앞에서 에라토스테네스의 체를 사용해서 소수를 구하는 코드를 작성하고, 그 다음은 while문을 사용해서 테스트케이스 N을 입력받는다. while문은 6이하의 자연수가 들어오거나, 범위인 number보다 큰 수가 들어오거나, 0이 들어오면 종료된다.
그리고 혹시 골드바흐의 추측이 틀렸을 경우를 대비해서 hasGold 변수도 준비해놨다.
조건을 만족하는 N이 입력되면, 3부터 범위내의 숫자 중에서 N=a+b를 만족하는 두 개의 소수를 찾는다. 소수는 True로 저장돼있기 때문에 prime[i]와 prime[n-i] 모두 True인 경우를 찾으면 된다. 찾았다면, a=i, b=n-i가 되고 break를 통해 for문을 종료하면 된다.
https://www.acmicpc.net/problem/6588
ㅎㅎㅎ 이 문제 풀면서 진짜 계속 틀려서 미치는 줄 알았다. 변수명 잘못쓴다거나 뭔가 생각한 것과 로직이 살짝 다르다거나, 그리고 또 확인하는 과정에서 number를 100으로 설정해두고 고치지 않고 그대로 내서 틀린다거나..... 풀기 싫어서 대충대충 내느라 많이 틀렸던 것도 있는데 아무튼 좀 힘들었다..ㅠㅠ
