[BaeKJoon] 2960번: 에라토스테네스의 체 문제 풀이 (Python)

1일 최소 1문제 풀기! 2일차

오늘은 1일차의 백준 홈페이지에 있는 골드바흐의 추측 문제를 풀면서 계속 시간초과가 발생하여 

살짝 힌트를 얻기위해 검색해보니! 에라토스테네스의 체 문제를 활용하여 풀면 해결할 수 있다는 내용을 알게되어 먼저 풀게되었습니다.

2960번: 에라토스테네스의 체

먼저

에라토스테네스의 체란 무엇인가?

(위키백과를 참고하였습니다)

(사진출처 : 위키백과)

 

에라토스테네스는 한마디로 소수를 찾는 방법입니다.

 

방법은 

 

2부터 소수를 구하고자 하는 구간의 모든 수를 나열하고 

 

2는 소수이므로 먼저 소수를 모아두는 곳에 적어 둡니다.

 

그 다음 자기 자신인 2를 제외한 모든 2의 배수를 지웁니다.

 

그 다음 남아있는 수 중에서 3이 소수이므로 소수를 모아두는 곳에 또 적어 둡니다.

 

또 자기 자신인 3을 제외한 모든 3의 배수를 지워줍니다.

 

그러면 이제 다음으로 남아있는 5도 소수이므로 소수를 모아두는 곳에 적어둡니다.

 

다시 자기 자신인 5를 제외한 모든 5의 배수를 지워줍니다. / 이 과정을 계속 반복하면 원하는 구간의 모든 소수를 구할 수 있다고 합니다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키백과에 Python, C, JAVA로 코드가 구현되어있지만 직접 한번 Python을 활용해서 구현해보겠습니다.

def getPrimaryNum_Eratos(N):
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]

먼저 입력한 숫자의 크기보다 하나 더 긴 길이의 모든 값이 True로 되어있는 list를 만들어줍니다.

 

소수를 구하면서 2의 배수, 3의 배수를 지워나가니 처음부터 끝까지 값을 확인할 필요가없으니

 

반복문을 활용해 절반 까지만 확인합니다.

 

그 다음 위의 방법대로 각각의 배수가 나올때마다 True에서 False로 바꿔준 다음 True인 인덱스만 모아 return 하도록 하였습니다.

 

자 여기서 이제 백준 2960번 문제를 보면 그저 에라토스테네스의 체 문제를 푸는 것이 아니었습니다.

 

문제 풀이

백준 문제는 단순하게 소수를 찾는 것이아닌

입력받은 N 이내의 소수를 찾기위해서 지워졌던 수들 중에서 K번째의 수를 찾는 문제였습니다.

N, K = map(int, input().split())

cnt = 0

nums = [True] * (N + 1)
for i in range(2, len(nums) + 1):
    for j in range(i, N+1, i):
        if nums[j] == True:
            nums[j] = False
            cnt = cnt + 1
            if cnt == K:
                print(j)
                break

아까의 코드에서 지울때마다 카운트하는 변수 그리고 반복문을 수정해주었습니다.

그럼 이제 다시 골드바흐의 추측문제를 풀어보아야겠습니다.

 

읽어주셔서 감사합니다.

 

 

SOMJANG/CODINGTEST_PRACTICE