백준 알고리즘 4948번: 베르트랑 공준 C언어

문제 출처: https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

1. 코드

#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;
}

2. 문제 해결 방식

나는 이 문제를 먼저 배열을 이용하여 소수 판별을 마친 뒤 n보다 크고, 2n보다 작거나 같은 소수의 개수를 파악하고 출력하여 마무리하기로 했다. 그렇다면 우선 배열을 선언하는데 문제를 읽어보면 n의 크기가 123456 이하이다. 그렇다는 것은 아무리 크더라도 246912라는 것이다. 그런데 배열을 5라고 선언하면 0부터 4까지이므로 246913만큼 선언한다.

그리고 0번째와 1번째는 절대 소수가 될 수 없기 때문에 1로 초기화한다. 1로 초기화하는 이유는 소수 아닌 수를 1로 구분하고 소수인 수를 0으로 구별하기 위해서이다. 그리고 반복문을 사용하는데 아까 1은 절대 소수는 될 수 없기 때문에 2부터 반복문을 시작하고 246913 / j 미만으로 반복하는데 그 이유는 1부터 10까지의 소수를 찾는다고 생각했을 때 1은 아니니까 제외하고 2부터 시작하면 2를 제외한 2의 배수는 소수가 아니다. 그리고 3으로 넘어가는데 3의 2 배수는 이미 판별되었기에 3의 3배부터 판별하면 되기에 i의 값은 j * j인 것이다. 그리고 이것을 따라가다 보면 4일 때는 4의 2 배수와 3 배수는 이미 판별이 되었기에 4의 4 배수부터 판별하면 되는데 우리는 10까지 판별하는 것이므로 굳이 시간을 소모하며 16이 소수인지 판별하지 않아도 되기에 3까지만 한다. j < 246913 / j도 마찬가지로 496의 배수까지만 판별하고 497부터는 이미 판별이 되었기에 비교하지 않는다.

반복문으로 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에 추가하고 그것을 출력하면 끝이다.

3. 느낀 점

생각보다 소수의 문제가 자주 나와서 조금 당황했다. 계속해서 원래 풀었던 방식을 계속해서 고수하는 느낌이라 뭔가 지루해지는 느낌이었다. 다음 수학 2의 문제는 소수가 아닌 다른 문제였으면 좋겠다.