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

[BanApp]

import sys
import math

def is_prime_num(n):
    arr = [True] * (n + 1)
    arr[0] = False
    arr[1] = False

    for i in range(2, int(math.sqrt(n)+1)):
        if arr[i] == True:
            j = 2
            while (i * j) <= n:
                arr[i*j] = False
                j = j + 1
    return arr

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    arr = is_prime_num(n)
    ans = []
    for i in range(len(arr)):
        if arr[i] == True:
            ans.append(i)
    x = n//2
    y = n//2

    while 1:
        if x in ans and y in ans:
            tmp = [x,y]
            tmp.sort()
            print(*tmp)
            break
        else:
            x = x + 1
            y = y - 1

문제에 소수가 나온다? 그럼 일단 에라토스테네스의 체 부터 만들자.
그렇게 되면 이제 n을 입력받을때 에라토스테네스의 체를 실행시키면 n보다 작거나 같은 소수들의 리스트 ans가 만들어 진다.
주어진 n을 반으로 나눠서(2의 배수이기 때문에 무조건 깔끔하게 반으로 나뉨) ans 리스트 안에 있는지 확인하고 없다면 각각 1을 증가,감소 시켜서 ans안에 있는지 확인을 한다. 만약에 값이 존재한다면 오름차순으로 출력해주면 정답이다. SO.. EZ..

[ghdcksgml1]

에라토스테네스의 체의 매력에 빠지신것같군요.

https://www.acmicpc.net/problem/1016

이 문제 아주 재밌습니다. 나중에 한번 풀어보셔요

[BanApp]

확인했습니다ㅎㅎ