C 언어로 에라토스테네스의 체 구현 방법

소개

이 실습에서는 주어진 상한까지의 소수를 찾기 위해 에라토스테네스의 체 알고리즘을 C 언어로 구현하는 방법을 배웁니다. 사용자로부터 상한을 입력받은 후, 소수의 배수를 소수가 아닌 것으로 표시하고, 마지막으로 찾은 모든 소수를 출력합니다. 이 실습은 C 프로그래밍 언어를 사용하여 수론 및 이산수학의 개념을 다룹니다.

이 실습은 세 가지 주요 단계로 구성됩니다. 상한을 입력받는 단계, 소수의 배수를 소수가 아닌 것으로 표시하는 단계, 그리고 찾은 모든 소수를 출력하는 단계입니다. 이러한 단계들을 따르면 에라토스테네스의 체 알고리즘과 C 언어에서의 구현에 대한 심층적인 이해를 얻을 수 있습니다.

상한값 입력

이 단계에서는 C 언어로 에라토스테네스의 체 알고리즘을 위한 상한값을 읽는 방법을 배웁니다. 상한값은 찾고자 하는 소수의 범위를 결정합니다.

먼저, 구현을 위한 새로운 C 파일을 생성합니다.

cd ~/project
nano prime_sieve.c

이제 상한값을 읽는 초기 코드를 작성합니다.

#include <stdio.h>

int main() {
    int upper_limit;

    printf("소수를 찾기 위한 상한값을 입력하세요: ");
    scanf("%d", &upper_limit);

    printf("입력된 상한값: %d\n", upper_limit);

    return 0;
}

프로그램을 컴파일하고 실행합니다.

gcc prime_sieve.c -o prime_sieve
./prime_sieve

예시 출력:

소수를 찾기 위한 상한값을 입력하세요: 50
입력된 상한값: 50

코드를 자세히 살펴보겠습니다.

scanf()를 사용하여 사용자로부터 정수 입력을 받습니다.
%d 형식 지정자는 scanf()가 정수를 읽도록 지시합니다.
입력값을 upper_limit 변수에 저장합니다.
그런 다음 입력된 상한값을 출력하여 입력을 확인합니다.

소수의 배수 표시

이 단계에서는 에라토스테네스의 체 알고리즘의 핵심 논리를 구현하여 소수의 배수를 소수가 아닌 것으로 표시합니다.

이전의 prime_sieve.c 파일을 수정합니다.

cd ~/project
nano prime_sieve.c

배열을 포함하고 배수를 표시하도록 코드를 업데이트합니다.

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("소수를 찾기 위한 상한값을 입력하세요: ");
    scanf("%d", &upper_limit);

    // 소수와 합성수를 표시하기 위한 불리언 배열 생성
    bool is_prime[upper_limit + 1];

    // 처음에는 모든 수를 소수로 초기화
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 각 소수의 배수를 합성수로 표시
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // p 의 배수를 합성수로 표시
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    printf("배수 표시 완료.\n");

    return 0;
}

프로그램을 컴파일하고 실행합니다.

gcc prime_sieve.c -o prime_sieve
./prime_sieve

예시 출력:

소수를 찾기 위한 상한값을 입력하세요: 50
배수 표시 완료.

에라토스테네스의 체 논리를 자세히 살펴보겠습니다.

소수와 합성수를 추적하기 위한 불리언 배열 is_prime을 생성합니다.
처음에는 모든 수를 소수로 표시합니다.
2 부터 제곱근 (upper_limit) 까지의 수를 반복합니다.
각 소수에 대해 그 배수를 합성수로 표시합니다.
알고리즘을 최적화하기 위해 p^2 부터 표시를 시작합니다.
내부 루프는 p 만큼 증가하여 p 의 모든 배수를 표시합니다.

모든 소수 출력

이 단계에서는 지정된 범위 내에서 찾은 모든 소수를 출력하여 에라토스테네스의 체 구현을 완료합니다.

prime_sieve.c 파일을 수정하여 출력 기능을 추가합니다.

cd ~/project
nano prime_sieve.c

소수를 출력하도록 코드를 업데이트합니다.

#include <stdio.h>
#include <stdbool.h>

int main() {
    int upper_limit;

    printf("소수를 찾기 위한 상한값을 입력하세요: ");
    scanf("%d", &upper_limit);

    // 소수와 합성수를 표시하기 위한 불리언 배열 생성
    bool is_prime[upper_limit + 1];

    // 처음에는 모든 수를 소수로 초기화
    for (int i = 2; i <= upper_limit; i++) {
        is_prime[i] = true;
    }

    // 각 소수의 배수를 합성수로 표시
    for (int p = 2; p * p <= upper_limit; p++) {
        if (is_prime[p]) {
            // p 의 배수를 합성수로 표시
            for (int i = p * p; i <= upper_limit; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 모든 소수 출력
    printf("%d까지의 소수는 다음과 같습니다:\n", upper_limit);
    for (int p = 2; p <= upper_limit; p++) {
        if (is_prime[p]) {
            printf("%d ", p);
        }
    }
    printf("\n");

    return 0;
}

프로그램을 컴파일하고 실행합니다.

gcc prime_sieve.c -o prime_sieve
./prime_sieve

예시 출력:

소수를 찾기 위한 상한값을 입력하세요: 50
50까지의 소수는 다음과 같습니다:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

마지막 단계를 자세히 살펴보겠습니다.

배수 표시 후 is_prime 배열을 반복합니다.
소수로 표시된 숫자만 출력합니다.
출력 결과는 사용자가 지정한 상한값까지의 모든 소수를 보여줍니다.

요약

이 실험에서는 먼저 C 언어로 에라토스테네스의 체 알고리즘의 상한값을 읽는 방법을 배웠습니다. prime_sieve.c라는 C 파일을 만들고 사용자에게 상한값을 입력하도록 프롬프트하고 upper_limit 변수에 저장하는 코드를 작성했습니다. 그런 다음, 소수와 합성수를 표시하기 위한 불리언 배열을 만들어 에라토스테네스의 체 알고리즘의 핵심 논리를 구현했습니다. 모든 숫자를 처음에는 소수로 초기화한 후 각 소수의 배수를 합성수로 표시했습니다. 마지막으로 지정된 상한값 내의 모든 소수를 출력하는 방법을 배웁니다.

C 언어로 에라토스테네스의 체 구현하기

소개

상한값 입력

소수의 배수 표시

모든 소수 출력

요약