https://www.acmicpc.net/problem/4948
문제
> 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
> 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
> 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다.
(11, 13, 17, 19)
또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
> 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 접근
테스트 케이스로 여러 범위에 대해 소수를 구해야하므로
미리 에라토스테네스의 체를 이용해 문제에서 주어진 최대 범위 까지의 소수를 모두 구한다.
1부터 123456까지인데 입력받은 n과 2n까지 봐야하므로 123456이 들어왔을 때, 246912까지 소수를 구해줘야한다.
각 수마다 부울로 소수면 1, 아니면 0으로 표시해준다. 1부터 시작하므로 범위는 246913까지해준다.
체에서 범위를 i는 2부터 i의 제곱이 246912보다 작거나 같을 때 까지 봐준다. 왜나면 체에서 소수를 걸러네는 방식이 어떤 수의 배수들을 전부 걸러네는 방식을 쓰기 때문이다.
2부터 따라가보면 2x3, 2x4..가 있어 3은 3x3부터 4는 또 3x4로 3에서 처리돼서 4x4부터 보면된다. 즉 i의 제곱수 부터 봐주기 때문이다.
문제해결
> 에라토스테네스 체를 주어진 범위까지 구현해 소수를 걸러준다.
> 0과 1은 소수가 아니므로 직접처리해주고 2부터 246912의 제곱근까지의 배수를 돌며 해당하는 수는 false로 마킹해준다.
> main함수에서 체를 호출해 소수를 만들어주고 while문으로 0이 입력되지않으면 무한 루프로해서 돌려준다.
> 입력받은 n에대해 n보다 크면서 2n보다 작거나 같은 범위에서 찾아야하므로 n+1부터 2n이하까지 반복문을 돌며 num벡터의 값이 1인 애들만 cnt에 수를 누적한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<bool> num(246913, true);
void sieve()
{
num[0] = false;
num[1] = false;
for (int i = 2; i*i <= 246912; i++)
{
if (!num[i]) continue;
for (int j = i * i; j <= 246912; j += i) num[j] = false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
sieve();
while (cin >> n && n != 0)
{
int cnt = 0;
for (int i = n + 1; i <= n * 2; i++) if (num[i]) cnt++;
cout << cnt << '\n';
}
}
후기
오랜만에 에라토스테네스체를 이용해서 구현이 헷갈렸는데 기본적인 원리는 알고있어서 됐다. 그래도 개념이 모호하니 다시 공부해보자.
입력으로 100000을 넣었는데 범위 오류가 났다.
분명 123456까지 범위를 줬는데 왜 그러나 싶었다.
생각해보니 2n까지의 범위를 봐야하기 때문에 10만이면 20만까지 탐색을 한다. 하지만 벡터는 123456까지 밖에 없기 때문에 범위 오류가 생긴것이다.
