C# 코딩테스트 강좌, 소수 구하기

문제 설명

주어진 자연수 N 이하의 모든 소수를 구하시오.

소수란, 1보다 큰 자연수 중에서 1과 자기 자신 외에는 약수가 없는 수를 말합니다. 예를 들어, 2, 3, 5, 7, 11, 13, 17, 19 등이 소수입니다.

입력

자연수 N (2 ≤ N ≤ 10,000,000)

출력

N 이하의 모든 소수를 한 줄에 하나씩 출력

예제

입력:
10

출력:
2
3
5
7

문제 해결 전략

소수를 구하는 데 가장 널리 알려진 알고리즘 중 하나는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘입니다. 이 알고리즘은 주어진 범위 내의 모든 소수를 효율적으로 찾을 수 있도록 돕습니다.

에라토스테네스의 체 알고리즘의 작동 방식은 다음과 같습니다:

2부터 N까지의 모든 숫자를 포함하는 배열을 생성합니다.
2는 소수이므로, 2의 배수는 소수가 아닐 것이므로 이를 배열에서 제거합니다.
다음으로, 남은 수 중 첫 번째 소수인 3을 선택하고, 3의 배수를 제거합니다.
이 과정을 배열의 끝까지 반복합니다. 남은 수가 소수입니다.

C# 구현

위의 방법을 사용하여 C# 언어로 소수를 구하는 프로그램을 구현해 보겠습니다:

using System;

class Program
{
    static void Main(string[] args)
    {
        // 사용자로부터 N 입력 받기
        Console.Write("자연수 N을 입력하세요 (2 ≤ N ≤ 10,000,000): ");
        int N = int.Parse(Console.ReadLine());

        // 소수 판별을 위한 벡터 배열 초기화
        bool[] isPrime = new bool[N + 1];

        // 모든 수를 소수로 초기화
        for (int i = 2; i <= N; i++)
        {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체 알고리즘
        for (int i = 2; i * i <= N; i++)
        {
            if (isPrime[i])
            {
                // i의 배수를 false로 설정
                for (int j = i * i; j <= N; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        // 결과 출력
        Console.WriteLine($"다음은 {N} 이하의 소수입니다:");
        for (int i = 2; i <= N; i++)
        {
            if (isPrime[i])
            {
                Console.WriteLine(i);
            }
        }
    }
}

코드 설명

입력 받기: 사용자에게 N을 입력하도록 요청합니다. 입력받은 값을 정수로 변환합니다.
소수 배열 초기화: N까지의 모든 수를 소수로 가정하여 true로 초기화하는 boolean 배열을 생성합니다.
에라토스테네스의 체 구현: 두 개의 중첩 루프를 사용하여 소수가 아닌 숫자를 false로 설정합니다. 외부 루프는 2부터 시작하고, 내부 루프는 i의 배수를 false로 설정합니다.
결과 출력: 최종적으로, 배열에서 true인 인덱스를 찾아 소수를 출력합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n log log n)이며, 공간 복잡도는 O(n)입니다. 이는 큰 범위의 소수를 찾는데 매우 효율적입니다.

결론

이번 강좌에서는 소수를 구하는 알고리즘을 소개하고, C#을 사용하여 이를 구현하는 방법을 설명했습니다. 에라토스테네스의 체는 매우 효율적인 소수 판별 알고리즘으로, 실제 코딩 테스트에서도 자주 출제되는 문제입니다. 소수의 개념을 이해하고 알고리즘을 구현해보는 것은 프로그래밍 실력을 향상시키는 데 큰 도움이 될 것입니다.

문제 설명

입력

출력

예제

문제 해결 전략

C# 구현

코드 설명

복잡도 분석

결론

관련