문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
[코드]
#include <stdio.h>
int main(void)
{
int N, cnt = 0;
int i, j, arr[246913] = {0, };
arr[0] = 1, arr[1] = 1;
for(j = 2; j < 246913 / j; j++)
{
if(arr[j] == 1) continue;
for(i = j * j; i < 246913; i += j)
if(i % j == 0) arr[i] = 1;
}
scanf("%d", &N);
while(N != 0)
{
cnt = 0;
for(i = N + 1; i <= N * 2; i++)
if(arr[i] == 0)
cnt++;
printf("%d\n", cnt);
scanf("%d", &N);
}
return 0;
}
문제해결방식
-
0번째와 1번째는 절대 소수가 될 수 없기 때문에 1로 초기화한다.
-
1로 초기화하는 이유는 소수 아닌 수를 1로 구분 | 소수인 수를 0으로 구별
-
2부터 반복문을 시작한다. 246913/J 미만으로 반복하는데 그 이유는 1부터 10까지의 소수를 찾는다고 생각했을 때 1은 아니니깐 제외하고 2부터 시작하면 2를 제외한 2의 배수는 소수가 아니다.
-
3으로 넘어가게 되면 3의 2 배수는 이미 판별되었기에 3의 3배부터 판별하면 되기에 J * J다.
-
반복문으로 arr[j] == 1일때, continue를 사용하는 것은 이미 소수로 판별한 것을 또 다시 비교할 이유가 없기 때문에 불 필요한 시간을 절약하기 위해서다.
-
i = j * j는 위에서 설명하였고 증감식에 i++가 아닌 i += j를 한 이유는 하나씩 더한다면 시간 소모가 커서 어차피 j의 배수만 확인하면 되기 때문에 i += j로 하였다.
-
이렇게 배열의 인덱스 값을 이용하여 소수 판별을 마치고 N값을 입력받고 while문을 이용하여 N의 값이 0이라면 종료하게 한다.
-
그리고 원활한 계산을 위해 반복문을 실행할 때마다 cnt값을 0으로 한다. 그리고 문제에서 n보다 크고, 2n보다 작거나 같은 소수의 개수이므로 i의 값을 N + 1로 하여 n보다 초과시키고 i <= N * 2로 2n보다 작거나 같은 소수의 범위를 설정한다.
-
그리고 1씩 증가시켜서 조건문을 이용하여 배열의 값이 0인 것을 나올 때마다 cnt에 추가하고 그것을 출력하면 끝이다.
출처: https://travelerfootprint.tistory.com/50 [나그네의 발자취:티스토리]
출처| https://www.acmicpc.net/problem/4948
