[백준] 2960번 에라토스테네스의 체 (파이썬)

에라토스테네스의 체

다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

동작 과정

1. 2부터 N까지의 모든 자연수를 나열한다.

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.)

4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

 

 

에라토스테네스의 체 알고리즘 (파이썬)

import math

n = 100    #2부터 100까지의 모든 수에 대하여 소수 판별
prime = [True for i in range(n+1)]  # 처음엔 모든 수가 소수(True)인 것으로 초기화

for i in range(2, int(math.sqrt(n))+1): #2부터 n의 제곱근까지의 모든 수를 확인하며
    if prime[i] == True:    #i가 소수인 경우(남은 수인 경우)
        #i를 제외한 i의 모든 배수를 지우기
        j = 2   
        while i * j <= n:
            prime[i * j] = False
            j += 1
#모든 소수 출력
for i in range(2, n+1):
    if prime[i]:
        print(i, end =" ")

 

 

참고 https://freedeveloper.tistory.com/392

---

 

 

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

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 입력 1 복사

7 3

예제 출력 1 복사

6

예제 입력 2 복사

15 12

예제 출력 2 복사

7

예제 입력 3 복사

10 7

예제 출력 3 복사

9

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

 

---

풀이 - 에라토스테네스의 체 알고리즘

 

위에서 공부한 에라토스테네스의 체 알고리즘을 그대로 적용시키기만 하면 되는 문제는 아니다.

이 문제는 지워가면서 k번째의 지워진 수를 출력해야되는 문제이기 때문에 하나씩 지워가면서 순서를 기억해야된다.

 

 

첫 번째 답안

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

nums = [ i for i in range(2, N+1)]
erase = []
while len(nums) > 0:
    p = nums[0]     #아직 지우지 않은 수 중 가장 작은 수
    temp = []
    for i in range(len(nums)):
        if nums[i] % p == 0:
            erase.append(nums[i])
        else:
            temp.append(nums[i])            
    nums = temp
    
print(erase[K-1])

 

이 코드는 erase 리스트를 만들어서 아직 지우지 않은 수 중 가장 작은 수인 p의 배수를 erase 리스트에 넣음으로써 순서를 기억할 수 있게 한 것이다.

그리고 아직 지워지지 않은 숫자들을 temp 리스트에 넣고 다시 nums 리스트에 대입함으로써 p도 갱신시키고 계속해서 다음의 배수를 지울 수 있게 한다.

 

 

두 번째 코드

n, k =map(int,input().split())
nums = [True] * (n+1)
cnt = 0
for i in range(2, n+1):
    if nums[i]:
        for j in range(i, n+1, i):  # 배수 값들을 false로
            if nums[j]:
                nums[j] = False
                cnt+=1
                if cnt == k:
                    print(j)

 

이 코드는 우선 모든 수들을 True (소수) 로 설정하고 2부터 차례대로 본인의 배수들을 False로 지정해줌으로써 지워준다. 그리고 cnt를 증가시켜서 해당 cnt가 입력값으로 받은 k와 같아지면 현재 지워진 수를 출력한다.