[1Day 1Algo] 백준 4948번 베르트랑 공준 (C++)

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

 

[단계별로 풀어보기 > 기본수학2] 에서 만난 문제다.

앞선 문제들이 모두 소수와 관련된 문제들이었다.

그래서 이 문제도 쉽게 해결할 수 있겠다는 생각이 있었으나, 2시간이나 걸리고 말았다.

 

 

이 문제는 1<= n <= 123456 의 제한이 있다.

나는 에라토스테네스의 체를 이용하기로 결심했기 때문에 (123456 * 2) + 1 의 배열을 만들어야 했다.

246913 의 크기를 갖는 배열을 말이다.

그러나 내가 만든 배열의 크기는...

246193 이었다.

엉뚱한 에라토스테네스만 붙잡고, 반례만 계속 찾았다!

정말 이런 허접하고 바보같은 실수는 하지 말아야겠다.

 

그 외에 새롭게 fill() 과 fill_n() 이라는 함수를 배웠다.

// https://stdcxx.apache.org/doc/stdlibref/fill.html
#include <algorithm>

namespace std {
  template <class ForwardIterator, class T>
   void fill(ForwardIterator start, ForwardIterator finish,
             const T& value);

  template <class OutputIterator, class Size, class T>
  void fill_n(OutputIterator start, Size n, const T& value);
}

이 함수들은 범위 내의 원소를 value로 채운다.

 

조금 쉽게 바꾸자면 아래와 같다.

fill(변경하려는 원소의 범위 시작주소, 변경하려는 원소의 범위 종료주소, 변경 값)

fill_n(변경하려는 원소의 범위 시작주소, 변경하려는 원소 갯수, 변경 값)

 

그 덕에 prime 배열을 true로 초기화 하는 작업이 간단하게 대체되었다.

 

 

#include <iostream>
#include <cmath>
#define MAX 246913
using namespace std;

int main() {
    bool prime[MAX];
    fill_n(prime, MAX, true);

    prime[0] = false;
    prime[1] = false;
    
    for (int i = 2; i <= sqrt(MAX); i++) {
        if (prime[i])
            for (int j = i * 2; j <= MAX; j += i)
                prime[j] = false;
    }

    while (true) {
        int n, sum = 0;
        cin >> n;
        if (n == 0) break;
        
        for (int i=n+1; i <= 2*n; i++)
            if (prime[i]) sum++;

        cout << sum << endl;
    }

    return 0;
}