[백준] 11502 세 개의 소수 문제

문제

• 임의의 홀수 K를 입력 받아서, 그 홀수가 어떻게 소수의 합으로 표현될 수 있는지 출력
  • 7 <= K < 1,000
• 여러 개의 답이 있다면 그 중 하나를 출력하고, 불가능하다면 0 출력

 

풀이

• 1000까지의 소수를 미리 구해두고, 3중 for문으로 합 표현이 가능한지 확인하기
• 시간 복잡도 : $O(N^3)$ 인데 1000까지의 소수 개수는 168개이므로 충분히 가능하다.

 

# 에라토스테네스의 체 이용한 소수 판별
def prime_number(x):
    prime = [True] * (x+1)                 # 소수인지 체크리스트
    for i in range(2, x+1):
        if prime[i]:
            for j in range(i*2, x+1, i):   # 소수의 배수 체크하기
                prime[j] = False
    
    # 소수인 숫자들만 리턴하기
    numbers = []
    for i in range(2, x+1):
        if prime[i] :
            numbers.append(i)
    return numbers

# 3개의 소수 합으로 나타낼 수 있는지 확인
def three_prime(numbers, K):
    for i in numbers:
        for j in numbers:
            for k in numbers:
                if i+j+k == K:
                    return (i, j, k)
                
    return 0

# 입력 받기
numbers = prime_number(1000)
for _ in range(int(input())):   # 각 테스트케이스에 대해
    K = int(input())
    print(*three_prime(numbers, K))

 

References

• 백준 11502번
• 2023.04.24 오늘의 문제