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

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

 

import math

# N, K 값을 입력받음
N, K = map(int, input().split())

# 2부터 N까지의 숫자를 집합으로 생성
lst = set([i for i in range(2, N + 1)])

# 소수 판별 함수 (에라토스테네스의 체를 사용하지 않음)
def is_prime_num(num):
    # 2부터 √num까지 나누어 떨어지는지 확인
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:  # 나누어 떨어지면 소수가 아님
            return False
    return True  # 나누어 떨어지지 않으면 소수

cnt = 0  # 제거한 숫자의 개수 카운트

while True:
    del_lst = set()  # 제거할 숫자를 저장할 집합
    for val in lst:  # 남아있는 숫자들 중 가장 작은 값을 선택
        if is_prime_num(val):  # 소수인지 판별
            # 해당 소수의 배수를 찾아 제거
            for val2 in lst:
                if val2 % val == 0:  # 소수의 배수이면 제거 대상
                    cnt += 1  # 제거한 개수 증가
                    del_lst.add(val2)  # 제거할 숫자 추가
                    if cnt == K:  # K번째로 제거된 숫자이면 출력 후 종료
                        print(val2)
                        exit()
        lst -= del_lst  # 제거할 숫자들을 전체 리스트에서 삭제
        break  # 한 번 루프 후 종료 (반복문을 여러 번 돌지 않도록)

 

 

GPT가 더 최적화된 코드를 제공했다.

 

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

arr = [True] * (N + 1)  # 모든 숫자를 소수(True)로 가정
cnt = 0  # 제거한 숫자의 개수 카운트

for i in range(2, N + 1):
    if arr[i]:  # i가 소수라면
        for j in range(i, N + 1, i):  # i의 배수를 모두 제거
            if arr[j]:  # 아직 제거되지 않은 숫자라면
                arr[j] = False  # 제거 처리
                cnt += 1  # 제거한 개수 증가
                if cnt == K:  # K번째로 제거된 숫자라면 출력 후 종료
                    print(j)
                    exit()