[Jungol] 정올 1901 소수 구하기

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1174&sca=20

 Input 

2

8

15

 

 Output 

7

13 17

① M이 소수인지 아닌지 확인

② M-i 혹은 M+i가 소수가 아닌지 확인합니다.

    (소수에 해당되느느 숫자 출력하고 종료)

 

※ 소수 여부 판단

소수는 1과 자기자신을 제외하고 나누어 떨어지지 않는 숫자를 의미합니다.

특정 숫자 Num이 소수인지 확인할 때, 2 ... Num-1까지 나누어 떨어지는지 확인하면 되지만

수학적으로는 Num의 제곱근까지 범위를 조정해도 상관없습니다.

ex) 9의 제곱근 = 3 → [2, 3]

     24의 제곱근 = 4.xx  → [2, 4]

     49의 제곱근 = 7 → [2, 7]

bool isPrime(int N) {
    if (N < 2) // 1은 소수 X
        return false;
 
    for (int i = 2; i * i <= N; ++i) {
        if (N % i == 0)
            return false;
    }
    return true;
}

API나 직접 제곱근을 구하는 함수를 구현할 수도 있지만

제곱근 자체가 두 수를 곱하면 원래의 결과가 나오는 것이므로 위와 같이 구현.

 

※ 문제의 숫자 범위가 큰 경우 i * i가 int 범위를 초과할 수 있습니다. 

그럴때는 아래와 같이 변경하여 표현도 가능합니다.

(소수 여부를 판단할 때는 에라토스트 테네스의 체도 유용합니다.)

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
bool isPrime(int N) {
    if (N < 2) // 1은 소수 X
        return false;
 
    for (int i = 2; i <= N / i; ++i) {
        if (N % i == 0)
            return false;
    }
    return true;
}
 
 
void output(int N) {
    if (isPrime(N)) { // N 자체가 소수인 경우
        printf("%d\n", N);
        return;
    }
 
    int flag = 0;
    for (int i = 1; !flag; i++) {
        // N으로 부터 i 크기 차이나는 숫자가 소수인지 확인
        if (isPrime(N - i)) {
            printf("%d ", N - i);
            flag++;
        }
        if (isPrime(N + i)) {
            printf("%d", N + i);
            flag++;
        }
    }
    puts("");
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int tc, N;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d", &N);
        output(N);
    }
}