백준 6588[골드바흐의 추측]

에라토스테네스의 체

• 주어진 범위 내의 모든 소수를 구하는 알고리즘

1. 2부터 n까지의 모든 자연수를 적는다.

2. 2를 제외한 모든 자연수를 지움

3. 3을 제외한 모든 자연수를 지움
   .
   .
   .

4. 위 과정을 반복하면서 지워지지 않은 수는 모두 소수임.

def goldbach():
    check = [True] * 10000

    for i in range(2, 101):
        if check[i] == True:
            for j in range(2*i, 10000, i):
                check[j] = False

    T = int(input())
    for _ in range(T):
        n = int(input())

        a = n //2
        b = a
        for _ in range(10000):
            if check[a] and check[b]:
                print(a, b)
                break
            a -= 1
            b += 1

goldbach()

에라토스테네스의 체를 이용해 작성한 코드

• check = [True] *10000 10000개의 true값을 가진 리스트 생성
• for i in range(2, 101) 100^2는 10000이므로, 2부터 101까지 for문 반복
• if check[i] == True: check의 i번째 값이 True이면(현재 모두 True이기 때문에 무조건 실행)
• for j in range(2*i, 10000, i): 2,3,5,7등의 배수를 찾아야 하기 때문에 i step씩 확인
• check[j] = False 해당 배수들 전부 False로 변경
• a = n // 2 입력받은 n값을 반으로 나눔
• b = a n을 반으로 나눈 값을 a, b에 나눠서 저장
• if check[a] and check[b]: check[a] 와 check[b]가 모두 소수이면 그대로 a,b값 출력 후 break로 for문 빠져나감
• a -= 1, b += 1
  둘 중 한 값이라도 소수가 아니면 a를 1빼고 b를 1더하면서 가장 가까운 소수 찾기