[알고리즘] 백준 11502 파이썬 - 세 개의 소수 문제

 

11502번: 세 개의 소수 문제

문제

정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다.

'5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 수도 있다.'

예를 들면,

• 7 = 2 + 2 + 3
• 11 = 2 + 2 + 7
• 25 = 7 + 7 + 11

5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램을 작성하시오.

 

문제풀이

#01
def ans(x,sosu):
    for i in sosu:
        for j in sosu:
            for k in sosu:
                if i+j+k==x:
                    print(i,j,k)
                    return
#02
n=997
sosu=[]
arr=[False,False]+([True]*(n-1))
for i in range(2,n+1):
    if arr[i]:
       sosu.append(i)
    for j in range(i*2,n,i):
        arr[j]=False
#03
for _ in range(int(input())):
    x=int(input())
    ans(x,sosu)

- #01 : 범위가 그렇게 크지 않기 때문에 브루트포스를 이용해도 시간초과가 발생하지 않는다.

           i,j,k에 #02에서 구한 sosu를 하나씩 넣어가며 i+j+k가 x가 되는 값을 구하여 출력한 후 return 한다.

- #02 : 에라토스테네스의 체를 이용하여 2부터 n까지의 소수를 구하여 sosu에 추가해준다.

- #03 : 입력받은 횟수만큼 for문을 반복하여 x에 해당하는 i,j,k값을 출력한다.