[백준] 14905번 소수 4개의 합

💡문제접근

• 입력값이 8미만인 경우 "Impossible."을 return하고 입력값이 8이상인 경우 에라토스테네스의 체를 이용해 소수를 걸러준 다음 4중 for문을 이용해서 입력값이 소수 4개의 합으로 표현이 된다면 출력하고 멈춘다.

💡코드(메모리 : 31256KB, 시간 : 44ms)

import sys
input = sys.stdin.readline

def func(x):
    if x < 8:
        return "Impossible."
    else:
        prime = []
        sieve = [True] * (x+1)
        sieve[0] = False
        sieve[1] = False
        for i in range(2, x+1):
            if sieve[i]:
                prime.append(i)
                for j in range(i*i, x+1, i):
                    sieve[j] = False

        flag = False
        for a in prime:
            if flag:
                break
            for b in prime:
                if flag:
                    break
                for c in prime:
                    if flag:
                        break
                    for d in prime:
                        if a + b + c + d > x:
                            break
                        if a + b + c + d == x:
                            ans = f"{a} {b} {c} {d}"
                            flag = True
                            break
        return ans

while True:
    N = input().strip()
    if N == "":
        sys.exit(0)
    else:
        print(func(int(N)))

💡소요시간 : 40m