백준 4948 - 베르트랑 공준

문제 https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

풀이

 

소수 찾는 문제는 에라토스테네스의 체를 항상 사용하는 듯 하다.

1부터 2n 까지의 소수를 찾는 게 아니라, n부터 2n까지의 소수를 찾는 문제라서 일단 처음부터 찾아준 후에,

n부터 몇개인지 count 했다.

 

에라토스테네스의 체는 2부터 소수를 찾아서 자기 자신을 제외한 배수들을 모두 지워서 소수를 찾아내는 방식이다. 

 

코드

#include <iostream>
using namespace std;

bool arr[123456*2];

int main()
{
    while(1)
    {
        int n;
        cin>>n;
        if(n==0) break;

        for(int i=0; i<=2*n; i++)
        {
            arr[i]=0;
        }

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