[Baekjoon] 1929번: 소수 구하기

✏️ 소수를 구하기 위한 알고리즘

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법

• N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
  N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문이다.

bool prime(int n) {
	if(n<2) {
	    return false;
	}
    for(int i=2;i<=n/2;i++) {
        if(n%i==0) {
            return false;
        }
    }     
}

• N이 소수가 되려면, 2보다 크거나 같고, 루트N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

bool prime(int n) {
	if(n<2) {
	    return false;
	}
    for(int i=2;i*i<=n;i++) {
        if(n%i==0) {
            return false;
        }
    }     
}

2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

• N이 너무 크면 위의 방법은 너무 오랜 시간이 걸린다.
  => 에라토스테네스의 체를 사용한다.

📌 에라토스테네스의 체
1. 2부터 N까지의 모든 수를 써놓는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 그 수의 배수를 모두 지운다.

<에라토스테네스의 체를 이용한 문제 풀이>

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

소스코드

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAX = 1000000;

int main(int argc, const char * argv[]) {
    int m, n;
    cin >> m >> n;
    bool check[MAX+1];
    check[0] = check[1] = true;
    
    for(int i=2;i<=n;i++){
        if(check[i]==false){
            for(int j=i+i;j<=n;j+=i){
                check[j] = true;
            }
        }
    }
    
    for(int i=m;i<=n;i++){
        if(check[i]==false)
            cout << i << "\n";
    }
    
    return 0;
}