코테 - 소수 판별하기: 5가지 방법

코딩테스트에서 자주 등장하는 소수 판별 문제를 C언어로 구현한 5가지 방법을 소개합니다. 각 방법은 효율성과 구현 방식에서 차이가 있으며, 다양한 상황에 적합한 접근법을 제공합니다.

방법 1: 기본 반복문

가장 직관적인 방법으로, 2부터 입력 숫자의 절반까지 나누기를 시도하여 소수를 판별합니다.

#include <stdio.h>

int isPrimeBasic(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("숫자를 입력하세요: ");
    scanf("%d", &num);
    if (isPrimeBasic(num))
        printf("%d는 소수입니다.\n", num);
    else
        printf("%d는 소수가 아닙니다.\n", num);
    return 0;
}
        

장점: 이해하기 쉽고 간단함

단점: 비효율적이며 큰 숫자에서 성능 저하

방법 2: 제곱근까지 확인

소수의 약수는 제곱근까지만 확인하면 충분하므로 반복 범위를 줄여 효율성을 높입니다.

#include <stdio.h>
#include <math.h>

int isPrimeSqrt(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("숫자를 입력하세요: ");
    scanf("%d", &num);
    if (isPrimeSqrt(num))
        printf("%d는 소수입니다.\n", num);
    else
        printf("%d는 소수가 아닙니다.\n", num);
    return 0;
}
        

장점: 기본 방법보다 훨씬 효율적

단점: math.h 라이브러리 필요

방법 3: 에라토스테네스의 체

특정 범위 내의 소수를 찾을 때 유용하며, 배열을 사용하여 소수를 판별합니다.

#include <stdio.h>
#include <stdlib.h>

int isPrimeSieve(int n) {
    if (n <= 1) return 0;
    int* sieve = (int*)calloc(n + 1, sizeof(int));
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                sieve[j] = 1;
            }
        }
    }
    int result = sieve[n] == 0 ? 1 : 0;
    free(sieve);
    return result;
}

int main() {
    int num;
    printf("숫자를 입력하세요: ");
    scanf("%d", &num);
    if (isPrimeSieve(num))
        printf("%d는 소수입니다.\n", num);
    else
        printf("%d는 소수가 아닙니다.\n", num);
    return 0;
}
        

장점: 큰 범위에서 여러 소수를 판별할 때 효율적

단점: 메모리 사용량이 큼

방법 4: 6k±1 최적화

모든 소수는 6k±1 형태로 나타낼 수 있다는 점을 이용해 확인 범위를 줄입니다.

#include <stdio.h>

int isPrime6k(int n) {
    if (n <= 1) return 0;
    if (n <= 3) return 1;
    if (n % 2 == 0 || n % 3 == 0) return 0;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return 0;
    }
    return 1;
}

int main() {
    int num;
    printf("숫자를 입력하세요: ");
    scanf("%d", &num);
    if (isPrime6k(num))
        printf("%d는 소수입니다.\n", num);
    else
        printf("%d는 소수가 아닙니다.\n", num);
    return 0;
}
        

장점: 불필요한 연산을 줄여 빠름

단점: 구현이 약간 복잡

방법 5: 재귀적 접근

재귀를 사용하여 소수를 판별하며, 교육적 목적에 적합합니다.

#include <stdio.h>

int isPrimeRecursive(int n, int i) {
    if (n <= 1) return 0;
    if (i * i > n) return 1;
    if (n % i == 0) return 0;
    return isPrimeRecursive(n, i + 1);
}

int main() {
    int num;
    printf("숫자를 입력하세요: ");
    scanf("%d", &num);
    if (isPrimeRecursive(num, 2))
        printf("%d는 소수입니다.\n", num);
    else
        printf("%d는 소수가 아닙니다.\n", num);
    return 0;
}
        

장점: 재귀의 개념을 이해하는 데 도움

단점: 큰 숫자에서 스택 오버플로우 가능성

결론

각 방법은 특정 상황에 따라 장단점이 있습니다. 코딩테스트에서는 시간 복잡도와 메모리 사용량을 고려하여 적절한 방법을 선택하는 것이 중요합니다. 일반적으로 제곱근 방법이나 6k±1 최적화 방법이 효율성과 간단함의 균형을 잘 맞춥니다.