3131. 100만 이하의 모든 소수 (D3)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE

< 입력 >

없음

< 출력 >

100만 이하의 모든 소수 출력하기

< 풀이 >

"에라토노스의 체"라는 이론을 사용할 것이다.

https://ko.wikipedia.org/wiki/%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

간단하게 설명하면

우선 100만 이하의 2의 배수를 모두 지운다.

다음으로 3의 배수를 모두 지운다.

진행 중 지워지지 않은 수를 만난다면 자신보다 작거나 같은 수 중에 나누어 떨어지는 수가 없다.

즉, 소수임을 의미한다.

따라서, 출력해주고 해당 수의 배수도 역시 지워주면 된다.

조금이라도 태스크를 줄여주기 위해 2의 배수는 짝수라는 특징이 존재하므로 2를 출력하고 3부터 진행한다.

true로 초기화된 100만 크기의 boolean 배열을 만든 뒤

3부터 값이 true라면 출력하고 100만보다 작거나 같은 수 중 배수를 모두 지운다.

false라면 소수가 아니라는 뜻이므로 continue하면 된다.

---

- 소스 코드 -

#include<iostream>
 
using namespace std;
 
bool arr[1000001];
 
int main(void){
    printf("2 ");
    fill_n(arr,1000001,true);
    for(int i=3;i<1000000;i+=2){
        if(i%2==1){
            if(arr[i]==true){
                printf("%d ",i);
                for(int j=i*2;j<=1000000;j+=i){
                    arr[j]=false;
                }
            }
        }
    }
    printf("\n");
}
 

---