N에 소수를 더해 가장 가까운 소수를 찾는 방법

이 글에서 다룰 문제는 다음과 같습니다. 주어진 수 N이 소수가 아니라면, 2부터 시작하는 소수를 차례대로 더해가면서 처음으로 소수가 되는 값을 찾아 출력하는 것입니다.

입력: N = 6
출력: 11

문제 이해 및 풀이 과정

예시를 통해 동작 원리를 살펴보겠습니다.

• N = 6은 소수가 아닙니다.
• 첫 번째 소수인 2를 더하면 6 + 2 = 8이 되지만, 8 역시 소수가 아닙니다.
• 다음 소수인 3을 더하면 8 + 3 = 11이 되고, 11은 소수입니다.

따라서 최종 결과로 11을 출력합니다.

알고리즘

START
Step 1 -> num = 15, i = num / 2 로 초기화한다.
Step 2 -> k = 2부터 k <= i까지 반복:
        - l = k / 2
        - j = 2부터 j <= l까지 반복하며 k의 약수 여부(flag)를 확인한다.
        - flag == 0이면 k는 소수이므로 num = num + k
        - a = num / 2
        - m = 2부터 m <= a까지 반복하며 num의 약수 여부(flag1)를 확인한다.
        - flag1 == 0이면 num은 소수이므로 num을 출력하고 종료한다.
STOP

C 언어 구현 예제

#include<stdio.h>
int main(){
    int num = 15;
    int i, k, j, sum = 0, flag = 0, l, flag1 = 0, a, m;
    i = num / 2;
    for(k = 2; k <= i; k++) {
        l = k / 2;
        for(j = 2; j <= l; j++) {
            flag = 0;
            if(k % j == 0) {
                flag = 1;
                break;
            }
        }
        if(flag == 0) {
            num = num + k;
        }
        a = num / 2;
        for(m = 2; m <= a; m++) {
            flag1 = 0;
            if(num % m == 0) {
                flag1 = 1;
                break;
            }
        }
        if(flag1 == 0){
            printf("%d", num);
            return 0;
        }
    }
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다. 초기값이 num = 15이므로, 첫 소수인 2를 더한 17이 소수가 되어 그대로 출력됩니다.

17

정리

이 알고리즘은 두 단계의 소수 판별 과정으로 구성됩니다. 먼저 후보 소수 k가 실제로 소수인지 검사하고, 소수라면 현재 값에 더한 뒤 그 결과가 소수인지 다시 검사합니다. 두 조건을 모두 통과하는 순간 결과를 출력하고 프로그램을 종료합니다. 시간 복잡도는 소수 판별에 제곱근 범위까지만 나눗셈을 시도하는 방식으로 최적화할 수 있으며, 큰 입력값에 대해서는 에라토스테네스의 체를 활용하는 것이 더 효율적입니다.