2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 풀이 """ N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. """ n,k = map(int, input().split()) list = [0] * (n+1) for i in range(2, n+1): list[i]=i cnt=1 # 1 지움 ch=True for i in range(2, n+1): if ch: for j in range(i, n+1, i): if list[j]!=0: if cnt==k: print(j) ch=False break cnt += 1 list[j]=0

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 분석 1 ≤ M ≤ N ≤ 1,000,000 이므로 일반적인 소수 구하기 방식으로 풀면 시간 초과 발생 ➔ 에라토스테네스 채 N의 제곱근까지만 탐색하는 이유 N의 제곱근이 n일 때 N=a*b를 만족하는 a b 전부 다 n보다 클 수 없음 N보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐 에라토스테네스의 체로 n이하의 수의 배수를 모두 제거하면 1부터 N사이의 소수를 구할 수 있음 N=16, n=4 a, b= (1,16),(2,8),(4,4)(8,2),(16,1) N보다 작..