C# 코딩테스트 강좌, 신기한 소수 찾기

현대의 소프트웨어 개발 환경에서는 코딩 테스트가 중요한 요소로 자리매김하고 있습니다.
기업들은 지원자의 알고리즘적 사고와 문제 해결 능력을 평가하기 위해 다양한 문제를 제시합니다.
이번 블로그에서는 신기한 소수 찾기라는 주제로 코딩 테스트 문제를 함께 풀어보도록 하겠습니다.

문제 설명

주어진 정수 N 이하의 모든 소수를 찾아서 출력하는 프로그램을 작성하시오.
단, 소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 자연수이며,
2 이상인 자연수 중에서 1과 자신만을 약수로 가지는 수를 뜻합니다.

입력

첫 번째 줄에 정수 N이 입력된다. (2 <= N <= 1000000)

출력

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

문제 접근 방법

소수를 찾는 문제에서 가장 일반적인 방법은 에라토스테네스의 체를 사용하는 것입니다.
이 알고리즘은 효율적이며 N의 크기가 큰 경우에도 사용할 수 있습니다.
에라토스테네스의 체를 사용하면 다음과 같은 순서로 소수를 찾을 수 있습니다.

2부터 N까지의 모든 수를 나열합니다.
2부터 시작하여 해당 수의 배수를 모두 제거합니다.
다음으로 남아 있는 수 가운데 가장 작은 수를 선택하고,
동일한 방식으로 해당 수의 배수를 제거합니다.
이 과정을 N의 제곱근보다 작은 수들에 대해 반복합니다.
남아 있는 수들은 모두 소수입니다.

C# 코드 구현

다음은 위의 알고리즘을 C#으로 구현한 코드입니다:

        
        using System;
        using System.Collections.Generic;

        class Program {
            static void Main(string[] args) {
                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가 소수인 경우
                        for (int j = i * i; j <= N; j += i) {
                            isPrime[j] = false; // i의 배수를 소수가 아님으로 설정
                        }
                    }
                }

                for (int i = 2; i <= N; i++) {
                    if (isPrime[i]) {
                        Console.WriteLine(i); // 소수 출력
                    }
                }
            }
        }

코드 설명

위 코드는 C#을 사용하여 에라토스테네스의 체 알고리즘을 구현한 것입니다.
각 줄을 자세히 살펴보며 설명하겠습니다.

using System;: C#의 시스템 네임스페이스를 사용하기 위해 추가합니다.
using System.Collections.Generic;: 리스트와 같은 컬렉션을 사용하기 위해 필요합니다.
int N = int.Parse(Console.ReadLine());: 사용자로부터 입력을 받아 N에 저장합니다.
bool[] isPrime = new bool[N + 1];: 0부터 N까지의 각 숫자가 소수인지 여부를 저장하기 위해 배열을 생성합니다.
for (int i = 2; i <= N; i++) { isPrime[i] = true; }: 모든 수를 소수로 초기화합니다.
for (int i = 2; i * i <= N; i++) { … }: N의 제곱근까지 반복하면서 소수를 찾습니다.
if (isPrime[i]) { … }: i가 소수라면, 그 배수를 모두 소수가 아님으로 설정합니다.
for (int i = 2; i <= N; i++) { if (isPrime[i]) { Console.WriteLine(i); }}: 최종적으로 남아 있는 소수를 출력합니다.

효율성

에라토스테네스의 체 알고리즘은 O(N log log N)의 시간 복잡도를 가지며,
공간 복잡도는 O(N)입니다. 따라서 N이 1,000,000과 같은 큰 수일지라도
충분히 빠르게 소수를 찾을 수 있습니다.

결론

이번 포스팅에서는 C#을 이용한 신기한 소수 찾기 문제를 해결하기 위해
에라토스테네스의 체 알고리즘을 사용하여 소수를 찾는 방법에 대해 알아보았습니다.
알고리즘 문제 해결 능력은 코딩 테스트 뿐만 아니라 실제 개발에서도 매우 중요하므로,
지속적인 학습과 연습을 통해 능력을 강화해 나가시기 바랍니다.
다음 포스팅에서는 보다 다양한 문제를 통해 알고리즘적 사고를 확장해보도록 하겠습니다.

문제 설명

입력

출력

문제 접근 방법

C# 코드 구현

코드 설명

효율성

결론

관련