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

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

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

 

1. 난이도 실버4 (🥈) 

 

2. 문제 해결 방법

에라토스테네스 체 복습할 겸 풀어봤다.

 

이 문제에선 소수도 지우는 수로 count 한다는 점을 주의해서 해결하면 된다.

 

n,k = map(int, input().split())

num = [True] * (n+1)

x = 0

for i in range(2,n+1):
  
  if num[i] == True:
    x += 1
    if x == k:
      print(i)
      break

    for j in range(2*i, n+1, i):
      if num[j] != False:
        x += 1
        if x == k:
          print(j)
          break
      num[j] = False

나는 2,3,5,7 등과 같은 소수일 때, 소수가 아닐 때를 각각 나눠서 count 해줬는데

 

구글링 해서 얻은 (비교적)숏코딩한 풀이가 아래에 있다.

 

n,k = map(int, input().split())

num = [True] * (n+1)

x = 0

for i in range(2,n+1):
  for j in range(i, n+1, i):
      if num[j] != False:
        num[j] = False
        x += 1
        if x == k:
          print(j)