백준 4948번 (C++)

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int n;
    int count = 0;
    int array[246913];
    array[1] = -1;
    
    cin>>n;
    while(n != 0)
    {
        for(int i=2; i<=2*n; i++)
        {
            for(int j=2; i*j<=2*n; j++)
                array[i*j] = -1;
        }
        for(int i=n+1; i<=2*n; i++)
        {
            if(array[i] != -1)
                count++;
            array[i] = 0;
        }
        cout<<count<<"\n";
        count = 0;
        
        cin>>n;
    }
    return 0;
}

 

<설명>

앞전문제에 사용되었던 "에라토스테네스의 체" 알고리즘을 사용하여

입력된 n의 2배수까지 소수를 비교한 뒤,

소수가 아닌경우 (array[i] != -1) 개수를 증가시켰다

 

다음번 반복을 위해 count 증가 후 array[i]를 0으로 초기화 한다

최종적으로 count를 출력시킨다