백준 1929: 소수 구하기

문제

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

---

입력

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

---

출력

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

---

코드

#include <iostream>
#include <cmath>

using namespace std;

int main()
{   
    // :: Input
    int start, end;
    cin >> start >> end;

    // :: Array
    bool* isNotPrime = new bool[end + 1];
    isNotPrime[0] = true;
    isNotPrime[1] = true;

    // :: Process
    string result = "";
    // :: 소수인지 판별 할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나게 됩니다. 
    // :: 따라서 소수인지 판별할때는 그 자연수의 제곱근 이하의 수까지만 검사를 하면 됩니다.
    // :: 출처: https://velog.io/@tmpks5/Algorithm-소수를-판별하는-방법-제곱근-나누기
    for (int i = 1; i <= sqrt(end); i++)
    {
        // :: Skip if not prime
        if(isNotPrime[i] == true) continue;
        
        // :: Mark as not prime
        for (int j = i * 2; j <= end; j += i)
        {
            isNotPrime[j] = true;
        }
    }
    
    // :: Output
    for (int i = start; i <= end; i++){
        if (isNotPrime[i] == false){
            result += to_string(i) + "\n";
        }
    }
    cout << result;
    return 0;
}

---

참고