[BOJ 4948] 베르트랑 공준

문제출처

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

소스코드

 반복문을 돌때마다 소수를 구하는것은 비효율적이라 생각하여 먼저 에라토스테네스체를 이용하여 범위안의 소수를 모두 구하고 반복문에서는 소수인 것만 판별하여 소수의 갯수를 출력.

#include <iostream>
#include <string.h>
#define MAX 246913
using namespace std;
 
/**
* n <= 123456 까지의 자연수 이므로 123456 * 2까지의 소수를 에라토스테네스체로 
* 먼저 구해 저장하고 while문을 돌면서 0이 나올때까지 그 값을 사용하는 방식으로 풀이. 
*/
bool isPrime[MAX];
 
void eratosthenes() {
    memset(isPrime, 1, sizeof(bool) * MAX);
    for (int i=2; i<=MAX; i++) {
        if (isPrime[i]) {
            for (int j=i*2; j<=MAX; j+=i) {
                isPrime[j] = 0;
            }
        }
    }
} 
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    eratosthenes();
    while(true) {
        int ans=0;
        cin>>n;
        if (n==0) {
            break;
        }
        for (int i=n+1; i<=2*n; i++) {
            if (isPrime[i]) {
                ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}