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

📌 문제

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

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

 

📌 문제 접근 방법

1. 2부터 N까지의 숫자 리스트를 생성한다.
2. 가장 작은 수가 소수라면 그 수의 배수를 모두 리스트에서 제거한다.
   (나중에 생각하고 알게 된 점이지만, 어차피 가장 작은 수는 항상 소수이므로 소수판별을 생략해도 된다.)

 

📌 코드

def is_prime(number):
    for i in range(2, number):
        if not number%i:
            return False
    else:
        return True


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

numbers = []
for i in range(2, N+1):
    numbers.append(i)

i = 0 
cnt = 0
while cnt < K:
    temp = numbers[i]
    if is_prime(temp):
        for number in numbers:
            if not number%temp:
                numbers.remove(number)
                cnt += 1
                if cnt == K:
                    break
    else:
        i += 1

print(number)

 

+)

n, k = map(int, input().split())
prime = [False for _ in range(n+1)]
ans = 0
for i in range(2, n+1):
    temp = i
    while temp < n+1:
        if prime[temp] == False:
            prime[temp] = True
            k -= 1
            if not k:
                ans = temp
                break
        temp += i
    if ans:
        break

print(ans)

이런 식으로 True/False로 표현해주면 이를 응용할 때, 해당 숫자를 인덱스로 하는 값을 통해 소수인지 바로 판별할 수 있다.