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

---

 

백준 - 단계별로 풀어보기 [1929] 

https://www.acmicpc.net/problem/1929

문제

 

 

자연수 N과 M이 주어졌을 때, M과 N 사이에 존재하는 소수를 한 줄씩 출력하는 프로그램을 작성하는 문제이다.

 

풀이

 

2581번 문제에서 사용했던 에라토스테네스의 체를 사용하면 풀 수 있는 문제이다.

N과 M중 더 큰 값인 N까지 존재하는 모든 소수를 bool prime 배열에 인덱스를 활용하여 나타내고,

M보다 크고 N보다 작은 소수를 모두 출력해주면 된다.

 

 

코드

 

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

int main() {
    int min,max;
    bool *prime;
    cin >> min;
    cin >> max;
    prime = new bool[max+1];
    fill_n(prime, max+1, 1);
    prime[0] = false;
    prime[1] = false;

    for (int i = 2; i <= sqrt(max); i++)
        if(prime[i] == true)
            for(int j = i*2; j <= max; j += i)
                prime[j] = false;

    for (int i = min; i <= max; i++)
        if(prime[i] == true)
            cout << i << "\n";
   return 0;
}

 

 

평가

 

에라토스테네스의 체를 활용한다면 금방 풀 수 있는 문제이다.

에라토스테네스의 체가 무엇인지 궁금하다면 링크를 참고하자.

 

2020/02/12 - [Algorithm/Baekjoon BOJ] - [백준 / BOJ] - 2581번 소수 C++ 풀이