#include <iostream>
int main(int argc, char **argv){ // 소수 - 에라토스테네스의 체
int M, N;
int a[1000001];
scanf("%d %d",&M,&N);
//소수 판별 범위까지 배열 생성, 값 넣어주기, 해당 수의 배수인 것 하나씩 지워나가기
for(int i=2; i<=1000000; i++) {
a[i] = i; // 배열 초기화 (인덱스의 숫자로)
}
for(int i=2; i<=1000000; i++) {
if(a[i]==0){
continue; // 이미 지워진 수 -> 건너뛰기
}
for(int j=2*i; j<=1000000; j+=i) { // 지워진 수 아닌 경우(소수) -> 배수 전부 지우기
a[j] = 0; // j의 첫번째 배수에서 수 끝까지, j = j + i (다음 배수 i만큼 더하는 것과 같다)
}
}
for(int i=M;i <= N;i++) {
if(a[i]!=0) {
printf("%d ", a[i]); // 소수 출력
}
}
return 0;
}
에라토스테네스의 체는 배열을 이용하여 소수를 구하는 알고리즘이다.
소수 판별 범위까지 배열을 생성하고 인덱스에 해당하는 값을 넣어 초기화해준다.
2부터 순회하면서 만약 배열의 값이 0 (지워진 상태)이 아닌 경우 소수로 보고 해당 수의 배수를 모두 지운다(배수이면 소수가 아니다)