1929번 소수 구하기(에라토스테네스의 체)

#문제링크 : https://www.acmicpc.net/problem/1929

M ~ N까지의 숫자 중 소수 구하기 / sel : 1~N까지의 숫자가 소수가 아니면 1, 소수이면 0이 저장될 bool 배열

답코드 참고 : https://medium.com/@reki318/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-6b07b060411

전략 : 1은 소수가 아니기에, sel[1]=true로 해놓고, 인덱스 2부터 sel[i]가 false라면 i를 포함하지 않는 i의 배수 인덱스에 전부 true를 대입한다. i x j의 값이 N을 초과할 때는 계산할 필요가 없으므로 break한다. i를 sqrt(N)까지만 반복하는 이유는 "N = 작은 인수 x 큰 인수"로 나타낼 수 있고 [작은 인수의 최대값 = 큰 인수의 최소값 = sqrt(N)]이므로 i는 작은 인수를 의미해서 sqrt(N)까지 반복하게 된다. 반면 j는 2~N까지 전부 돌아야 한다. 이유는 [작은 인수~큰 인수]의 범위를 모두 가져야 N까지의 배수들을 전부 true로 만들어서 제외시킬 수 있기 때문이다. 그리고 마지막에 M인덱스부터 N인덱스까지 sel[i]가 false인 i를 출력하면 M~N의 소수들이 출력된다.

Code