[Python] BOJ 2960 에라토스테네스의 체

[URL] : https://www.acmicpc.net/problem/2960

문제

풀이

from sys import stdin

n, k = map(int, stdin.readline().split())
cnt = 0

arr = [True] * (n+1)

for i in range(2, n+1):
	for j in range(i, n+1, i):
		if arr[j]:
			arr[j] = False
			cnt += 1
			if cnt == k:
				print(j)
				break

알게된 점

드디어 유명한 에라토스테네스의 체 문제를 풀어보았다. 소수 문제 풀때마다 들었던

문제 설명에 자세히 써있는 문제의 알고리즘에 따라 코드를 작성했다고 생각했다. 결국은 런타임 에러..

input() 을 sys.stdin.readline()으로 바꿔서 넣어줘도 PyPy3로 돌려보아도 계속 런타임 에러가 떴다.

내가 짠 코드에 문제가 있다는 뜻이겠지.. 겸허히 받아들이고 코드를 보았는데 while문과 for문의 대잔치

결국은 서치 끝에 문제를 풀 수 있었다.

1. 2부터 n까지의 리스트를 따로 만들어 줄 필요없이 2부터 n까지 for문을 돌린다

2. 해당 숫자가 지워졌는지 있는지 확인하기 위해 따로 arr를 만들어 준다