[11502] 세 개의 소수 문제 (Python)

문제

---

11502번: 세 개의 소수 문제

풀이

---

이 문제는 여러 가지 테스트케이스에서 어떤 수가 주어졌을 때, 세 개의 소수의 합으로 나타낼 수 있는지를 확인하는 문제입니다.

그렇다면 우선 소수를 걸러내는 에라토스테네스의 체가 필요할 것이며, 매 테스트 케이스마다 소수를 새로 구하지 않고 한 번만 계산하는 것이 좋아 보입니다.

 

소수들을 찾았으면 소수들의 합으로 나타내야 합니다.

이는 세번의 for문으로도 충분히 풀리게 되는데 그 이유는 1000까지의 소수의 개수가 168개 이므로 168*168*168 = 4741632로 시간초과 기준인 1억에 한참 못 미치기 때문입니다.

 

하지만 for문을 중첩으로 돌릴 시, 적당한 케이스를 발견하면 그 즉시 중단해야 하는데 이 부분을 구현하기 위해서는 두 가지 flag를 사용하거나 try, exception으로 구현할 수 있습니다.

저는 후자가 구현에 더 편리하기 때문에 다음과 같이 구현했습니다.

 

코드

---

prim_num_list = [False,False]+[True for _ in range(999)]
for i in range(2,1001):
    if prim_num_list[i] == True:
        for j in range(2*i,1001,i):
            prim_num_list[j] = False

prim_num_index = []
for index,i in enumerate(prim_num_list):
    if i == True:
        prim_num_index.append(index)


for _ in range(int(input())):
    num = int(input())
    sum_num_list = [-1,-1,-1]
    try:
        for i in range(len(prim_num_index)):
            sum_num_list[0] = prim_num_index[i]
            for j in range(i,len(prim_num_index)):
                sum_num_list[1] = prim_num_index[j]
                for k in range(j,len(prim_num_index)):
                    sum_num_list[2] = prim_num_index[k]
                    if sum(sum_num_list) == num:
                        print(*sum_num_list)
                        raise()
        print(0)
    except:
        continue