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

글에 개요

백준 알고리즘 2960번 "에라토스테네스의 체" 문제입니다. 에라토스테네스의 체 개념을 알면 쉽게 해결할 수 있습니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

에라토스테네스의 체 (Sieve of Eratosthenes)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

이 후 이 문제를 통해 확장할 수 있는 문제가 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 2960] 에라토스테네스의 체: https://www.acmicpc.net/problem/2960

참고할 글

1. http://brenden.tistory.com/48 ([알고리즘] 에라토스테네스의 체 정리글)

핵심 내용

1. 에라토스테네스의 체 개념을 묻는 문제이다.
2. 힌트를 보면 2,4,6,8,10,3,9,5,7 순으로 진행되는 것을 보고 참고할 글 1번 코드에서 약간만 바꾸면 해결됩니다.
3. 17 line : int j = i *2가 아닌 i 부터 시작하면 됩니다.

해결 방법

1. 소수인지 아닌지 여부를 파악하기 위한 isPrime 배열의 초기화를 진행해 줍니다.
2. 이미 소수인지 아닌지 여부가 판별이 되지 않았다면 배열의 값을 false로 바꾸고 K번째의 수를 찾게 될 때까지 진행하면 됩니다.

해결한 코드

백준 참고 내용

에라토스테네스의 체 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	3949	1997	1762	52.223%

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 숫자 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 숫자를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 입력 1 

10 7

예제 출력 1 

9

힌트

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.