[백준/C++] 1929 번 : 소수 구하기 풀이

문제 1929 번 : 소수 구하기

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

1929번: 소수 구하기

 

문제

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

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

 

출력

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

---

단순한 소수 찾기로 구하면 메모리 초과가 발생한다. 에라토스테네스의 체 알고리즘을 사용해야  한다.

에라토스테네스의 체 란? 👇 

https://silver-g-0114.tistory.com/39?category=1094593

[Algorithhm] 에라토스테네스의 체 알고리즘이란?

---

 

풀이

#include <iostream>
#define MAX 1000001
using namespace std;

int m, n;
int arr[MAX];

void erathosthenes(){
    
    arr[0] = arr[1] = -1; // 0,1 : 소수 아님
    for(int i=2; i<MAX; i++){
        arr[i] = i;
    }
    
    for(int i=2; i*i<=MAX; i++){
        if(arr[i] == i){ // 아직 지워지지 않았을 경우
            for(int j=i*i; j<MAX; j+=i){ // j = i^2 + (i*n)
                if(arr[j] == j){
                    arr[j] = i; // i의 배수임을 표시 (소수가 아님)
                }
            }
        }
    }
}

int main(void){
    
    cin >> m >> n;
    
    erathosthenes();
    
    for(int i=m; i<=n; i++){
        if(arr[i]==i)
            cout << i << "\n";
    }
    
    return 0;
}

 

 

---

풀이 인증