[백준]1153 네개의소수 #소수#골드바흐의추측

1. 풀이

처음엔 에라토스테네스의 체를 이용하여 소수를 모두 구하고, dfs를 이용하여 구하려고 했다. (소스코드1)

(1)소수리스트가 정렬되어 있기 때문에 크기가 N보다 커지면 벡트래킹.

(2) i번째 숫자를 추가했을때 x값이 나오는 경우는 더이상 탐색하지 않기위해서 visited[i][x]를 관리해 주었지만 시간초과가 났다.

​

정답은 골드바흐의 추측을 응용해서 풀이하는것이였다. (소스코드2)

[골드바흐의 추측]

2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다.

이를 응용하면 가장 작은 네개의 소수로 만들 수 있는 수 8(2+2+2+2)이상의 숫자는 소수4개로 표현할 수 있다는 뜻인데 그 방법은 다음과 같다.

​

(1) N이 짝수일때

N이 짝수일때는 N-4도 짝수이다. (N-4>=4)

따라서 N-4를 두개의 소수의 합으로 표현하고 (N-4=a+b), 4를 2+2로 표현하면

N=a+b+2+2로 표현할 수 있다.

​

(2) N이 홀수일때

N이 홀수일때는 N-5가 짝수가 된다. (N-5>=4)

따라서 N-5를 두개의 소수의 합으로 표현하고 (N-5=a+b), 5를 2+3으로 표현하면

N=a+b+2+3으로 표현할 수 있다.

​

2. 소스코드

(1) 소스코드1 (백트래킹, 시간초과)

import sys

def aratos():
    for i in range(2,N+1):
        if isPrime[i]:
            primeL.append(i)
            for j in range(i*i,N+1,i):
                isPrime[j]=0

def dfs(nowL,sumOfL):
    #백트래킹
    if sumOfL>N:
        return
    nowLSize=len(nowL)
    #종료조건
    if nowLSize==4:
        if sumOfL==N:
            print(*nowL)
            sys.exit()
        return
    for i in range(size):
        newSum=sumOfL+primeL[i]
        if newSum > N:
            return
        if visited[nowLSize][newSum]==0:
            visited[nowLSize][newSum]=1
            dfs(nowL+[primeL[i]],sumOfL+primeL[i])

N=int(input())
isPrime = [1 for i in range(N + 1)]
isPrime[0] = isPrime[1] = 0
primeL = []
visited=[[0 for j in range(N+1)] for i in range(4)]
aratos()
size=len(primeL)
dfs([],0)
print(-1)
​

 

(2) 소스코드2 (골드바흐의 추측, 통과)

import sys

def aratos():
    for i in range(2,N+1):
        if isPrime[i]:
            primeL.append(i)
            for j in range(i*i,N+1,i):
                isPrime[j]=0


N=int(input())
isPrime = [1 for i in range(N + 1)]
isPrime[0] = isPrime[1] = 0
primeL = []
aratos()
size=len(primeL)

def goldbach(num):
    for i in range(size):
        for j in range(size):
            sumOfNum=primeL[i]+primeL[j]
            if sumOfNum==num:
                ans.extend([primeL[i],primeL[j]])
                return
            elif sumOfNum>num:
                break


if N<8:
    print(-1)
else:
    #짝수이면
    if N%2==0:
        ans=[2,2]
        N-=4
        goldbach(N)
        print(*ans)
    #홀수이면
    else:
        ans=[2,3]
        N-=5
        goldbach(N)
        print(*ans)