골드바흐의 추측 풀이

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

백준 알고리즘 기초 1/2 300에서 6번째 - 6588번 골드바흐의 추측을 풀어보았다.

 

풀이: 짝수를 두 홀수의 합으로 보일 수 있는지 알아보는 문제이다.

파이썬의 경우, 리스트를 쓰면 시간초과가 나서 에라토스테네스의 체 함수를 딕셔너리로 출력하게 해서 key의 value가 true면(소수이면) 합을 출력하게 했다.

 

C++

 

Python

import sys

def primes(n):
	sieve = [True] * n
	m = int(n ** 0.5)
	for i in range(2, m + 1):
		if sieve[i] == True:           
			for j in range(i+i, n, i): 
				sieve[j] = False
	return {i:sieve[i] for i in range(n)} # 유사 에라토스테네스의 체의 딕셔너리 형태

arr=primes(1000000)
while 1:
	s=int(sys.stdin.readline().rstrip())
	if s==0: break
	a=3 # 2는 제외
	b=s-3
	for i in range(1000000):
		if arr[a] and arr[b]:
			print(f'{s} = {a} + {b}')
			break
		a+=1
		b-=1
	else:
		print("Goldbach's conjecture is wrong.")

Java