백준 1929번 - 소수찾기 문제 프로그래밍 언어 [아라토스테네스의 체]

📍 백준 1929번 - 소수찾기 문제 프로그래밍 언어 [아라토스테네스의 체]

---

🧩문제 요약

<아라토스테네스의 체>

n과 m이 주어질 때 두 수사이의 소수를 모두 출력하라. 

---

👍이 문제에서 배운점

아라토스테네스의 체는 소수를 판별하는게 아니라 합성수를 지워나가는 개념이다. 

https://codinghago.tistory.com/99

소수찾기 알고리즘 C++, 에라토스테네스의 체

 

 

 

아라토스테네스의 체를 알고 있었지만 계속 배수만큼 수를 판별하려고 하다보니 코드가 복잡해졌다. 

아라토스테네스의 체는 소수를 판별하는 것이 아니라 순차적으로 합성수를 지워나가는 것인것을 기억하자. 

---

🧾 완성된 코드 

 

#include <iostream> 
#include <vector>
using namespace std; 

int main(){
    int m, n;
    cin >> m >> n ; 
    
    vector<int> arr(n+1, 0);
    for(int i = 2 ; i<n+1; i++){
        arr[i] =i; 
    }

    for(int i = 2; i< n+1; i++){
        if(arr[i] == 0) continue; 
        for(int j = i*2 ; j<n+1; j+=i){
            if(arr[j]!=0) arr[j] = 0;
        }
    }

    for(int i = m; i< n+1; i++){
        if(arr[i] !=0 ){
            cout << i << "\n";
        }
    }

}

---

알고리즘을 알고 있어도 두루뭉술 알고있으면 활용을 전혀 할 수가 없다...