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