[Code Tree] 범위 내의 소수 2

범위 내 두 숫자를 포함한 그 사이의 소수 개수를 구하는 문제

 

에라토스테네스의 체를 이용하는 것이 보편적이고 빠른 소수구하는 알고리즘이다.

 

범위 내의 소수에 대해 소수의 배수를 제거해나가는 방식으로 2중 반복문을 사용한다.

 

#include <iostream>

using namespace std;

bool nums[1000001] = { 0, };

void setNums(){

    nums[1] = true;

    for(int n = 2; n < 1000001; n++){

        if(nums[n] == true) continue;

        for(int m = n + n; m < 1000001; m += n){

            nums[m] = true;

        }

    }

}

int main() {

    int n, m;

    cin >> n >> m;

    setNums();

    int cnt = 0;

    for(int i = n; i <= m; i++){

        if(nums[i] == true) continue;

        else cnt++;

    }

    cout << cnt;

    return 0;

}

 

* 에라토스테네스의 체

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체