[Baekjoon] 2960번 : 에라토스테네스의 체 (Python, 수학, 구현)

[Baekjoon] 2960번 : 에라토스테네스의 체 (Python, 수학, 구현)

 

목차

 

 

 

 

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

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

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 351B

 

 소수를 구하는 방법인 에라토스테네스의 체의 변형 문제로 counting을 통해 k번째의 삭제 숫자를 찾는 문제이다.

이에 맞도록 구현을 진행하면 된다.

 

n,k = map(int, input().split())
s = [i for i in range(2, n+1)]
cnt = 0
flag = False
while len(s) != 0:
    p = s[0]
    for i in range(len(s)):
        if s[i] % p == 0:
            cnt += 1
            tmp = s[i]
        if cnt == k:
            flag = True
            break
    if flag:
        break
    s = [i for i in s if i % p != 0]
print(tmp)

 

방법 2 - 메모리 30840KB / 시간 68ms / 코드 길이 307B

 

n,k = map(int, input().split())
s = [1]*(n+1)
cnt = 0
flag = False
for i in range(2, n+1):
    for j in range(i, n+1, i):
        if s[j]:
            s[j] = 0
            cnt += 1
            if cnt == k:
                print(j)
                flag = True
                break
    if flag:
        break