[백준][Python] 11502 세 개의 소수 문제 - 풀이 공유

https://www.acmicpc.net/problem/11502

11502번: 세 개의 소수 문제

주어진 5 이상의 홀수 K를 세 개의 소수의 합으로 나타낼 수 있는지 판별하는 문제였습니다.

먼저 이 문제를 풀기 위해서는 소수를 구하는 에라토스테네스의 체 알고리즘을 알고 있어야 합니다.

모르신다면 여기의 문제를 먼저 풀어보시기 바랍니다.

 

에라토스테네스의 체 알고리즘을 사용하여 주어진 K보다 작은 소수들을 구한 후

3중 for문으로 모든 경우를 탐색해보는 브루트 포스(Brute Force) 알고리즘 기법을 사용하여

K를 만들 수 있는 세 개의 소수를 찾아냈습니다.

 

<풀이>

def printSum(pL, s):
    for n1 in pL:
        for n2 in pL:
            for n3 in pL:
                if n1 + n2 + n3 == s:
                    print(n1, n2, n3)
                    return
    print(0)
 
 
def findPrime(num):
    data = list(range(2, num + 1))
    result = []
 
    while len(data) != 0:
        m = data[0]
        result.append(m)
        cnt = 0
        while cnt < len(data):
            if data[cnt] % m == 0:
                data.pop(cnt)
                cnt -= 1
            cnt += 1
 
    return result
 
 
T = int(input())
N = []
 
for i in range(T):
    N.append(int(input()))
 
for n in N:
    printSum(findPrime(n), n)

함수 findPrime:  num까지 숫자 중 소수 리스트를 반환한다.

함수 printSum:  소수 리스트 PL과 소수의 합으로 만들 s를 받아 s를 만들 세개의 소수를 출력한다.