관리 메뉴

솜씨좋은장씨

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

Programming/코딩 1일 1문제

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

솜씨좋은장씨 2020. 2. 8. 01:06
728x90
반응형

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

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

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

 

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

문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에

www.acmicpc.net

먼저

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

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

(사진출처 : 위키백과)

 

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

 

방법은 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수학에서 에라토스테네스의 체는 소수(소쑤)를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초

ko.wikipedia.org

위키백과에 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

Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

 

Comments