6588번 바로가기: https://www.acmicpc.net/problem/6588
17103번 바로가기: https://www.acmicpc.net/problem/17103

이 두개를 왜 같이 풀이하냐?

왜냐면 매우 비슷한 문제이기 때문
6588에서 몇줄 안고치고 제출해서 바로 맞췄다

에라토스테네스의 체

이 두 문제를 풀기 위해서 꼭 알고 넘어가야 하는 개념
일단 6588번 나의 첫번째 풀이

def sosu(x):
    for i in range(2,x):
        if x % i == 0:
            return False
    else:
        return True

arr = []

while True:
    num = int(input())
    if num == 0:
        break
    first,second = 0,0
    for i in range(3,num):
        if i % 2 != 0 and sosu(i) == True and (num-i) % 2 != 0 and sosu(num-i) == True:
            first = i
            second = num-i
            arr.append(f"{num} = {first} + {second}")
            break
        else:
            continue
    else:
        arr.append("Goldbach's conjecture is wrong.")

for i in arr:
    print(i)

당연히 장렬히 시간초과 폭탄을 맞아버리고...^^

나는 이 gif짤을 보고 바로 이해했다

6588번

import sys

sosu = [True] * 1000001 # 처음엔 모든 수가 전부 소수라고 가정
sosu[0],sosu[1]=False,False # 0,1은 제외

for i in range(2,1000001):
    if i*i > 1000000: break
    if sosu[i] == False: continue
    for j in range(i*i,1000001,i): # 2-> 4,6,8,10,...제외 (2로 나눠지니까 소수가 아님)
        sosu[j] = False

while True:
    num = int(sys.stdin.readline().rstrip())
    if num == 0:
        break
    for i in range(3,num,2):
        if sosu[i] == True and sosu[num-i] == True:
            print(f"{num} = {i} + {num-i}")
            break
        else:
            continue
    else:
        print("Goldbach's conjecture is wrong.")

먼저 소수배열을 만들어놓는다
그니까 sosu=[0,1,2,3,4,5,6,7,...]=[F,F,T,T,F,T,F,T...]
소수면 T, 아니면 F로 배열을 저장한다
저장방식은 만약 2이면 4부터 시작해서 2씩 커지는 4,6,8,10,...은 전부 2로 나눠지니까 소수가 아니므로 전부 F로 저장해준다. 이렇게 저장하다보면 언젠가 다 채워진다.

그 다음 입력받는 값에 따라 sosu배열에서 T이면 소수로 인식하는 방식으로 풀어주었다.

17103번

# 문제 이해가 안되서 찾아본 블로그 (문제 이해용으로만 봄 답은 안봄)
# https://greentea31.tistory.com/24

import sys
input = sys.stdin.readline

sosu = [True] * 1000001 # 처음엔 모든 수가 전부 소수라고 가정
sosu[0],sosu[1]=False,False # 0,1은 제외

for i in range(2,1000001):
    if i*i > 1000000: break
    if sosu[i] == False: continue
    for j in range(i*i,1000001,i): # 2-> 4,6,8,10,...제외 (2로 나눠지니까 소수가 아님)
        sosu[j] = False

n = int(input())
partition = 0
partition_arr = []

for i in range(n):
    num = int(input())
    for i in range(num):
        if sosu[i] == True and sosu[num-i] == True:
            if (i or num-i) not in partition_arr:
                partition_arr.append(i)
                partition_arr.append(num-i)
                partition += 1
        else:
            continue
    print(partition)
    partition = 0
    partition_arr = []

이것도 6588번에서 조금만 응용해서 풀어주면 된다.
소수 저장 배열은 그대로고 입력받는 방식만 조금 몇줄 바꿔주면 해결

한줄평

에라토스테네스의 체...
나를 너무 괴롭혔지만 이런 알고리즘을 알아놔야 코테에서 도움되겠지?ㅠㅠ 하나 배웠다