백준
1929번 소수 구하기(에라토스테네스의 체)
조주똥
2020. 5. 20. 15:14
#문제링크 : https://www.acmicpc.net/problem/1929
M ~ N까지의 숫자 중 소수 구하기 / sel : 1~N까지의 숫자가 소수가 아니면 1, 소수이면 0이 저장될 bool 배열
전략 : 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의 소수들이 출력된다.