백준 2960번 에라토스테네스의 체

< 백준 2960번 에라토스테네스의 체 - 마포 코딩박 >

사용한 알고리즘: 에라토스테네스의 체


 문제 자체가 그 유명한 에라토스테네스의 체를 구현하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 11~24)
 첫 for 문으로 i=2~N까지의 모든 i를 봅니다.
 두번째 for 문으로 j=i 의 배수( i, 2i, 3i, ... )들을 차례로 보며 bool[j] = true 로 한번 본 수를 체크합니다. 이를 통해 한번 본 수는 다시는 보지 않습니다. ( 문제에서 ' 지운다 ' 는 것을 bool 배열을 만들어 구현했습니다. )
 또한 지우는 횟수를 저장하여 K번째 지우는 수를 답으로 출력합니다.