[c#] 백준 알고리즘 1929 - 소수 구하기

소수을 구하는 알고리즘은 기본적으로 O(n) 시간 복잡도를 가지는데 이번 알고리즘 문제는 입력이 최대 1,000,000까지이므로 시간 복잡도를 더 최소화 하는 알고리즘을 사용해야 했다.

그래서 에라토스테네스의 체라는 알고리즘으로 구현을 해보았다.

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

문제풀이

알고리즘을 구현하기 위해 기본적인 소수를 찾는 알고리즘을 알고있어야한다.
소수란 1과 자기자신으로 밖에 나눌 수없는 수이다. 즉, 약수가 2개라는 소리인데.
ex) 17이 소수인지 확인 하기 위해서 2부터 16까지 나누어지는지 확인을 하고 나누어지지 않으면 소수라는 소리이다.

우선 가장 쉽게 구현할 수있는 소수를 구하는 코드를 작성하고 최적화를 해보자

---

1. 소수 구하기 [시간복잡도 O(n^2)]

int n = 100;
for (int i = 2; i <= n; i++)
{
    for (int j = 2; j <= i; j++)
    {
        if (j == i)
            Console.WriteLine(j);

        if (i % j == 0)
            break;
    }

}

이 코드는 100아래 수 중에서 소수를 찾는 방법이다. 외부 반복문 2에서 n까지 반복하고 내부 반복문은 2에서 i까지 반복하여 i가 2와 i-1 사이의 숫자로 나누어지는지 확인한다. 나누어지지 않으면 소수이며 콘솔에 출력된다.

이 코드는 매번 외부 반복문 마다 2부터 i-1까지 나누어주면서 소수인지 판별하게 되는데 시간이 너무 낭비된다.

"에라토스테네스의 체"라는 알고리즘을 알게되면 시간복잡도를 O(nlog * logn)로 줄일 수 있다. 알고리즘에 대해 알아보자.

---

에라토스테네스의 체 - 개념

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

[에라토스테네스의 체] 알고리즘은 작은 수 부터 소수를 찾고 소수의 배수를 소수 목록에 제외시키는 방법이다.

위키 백과에 시각화가 아주 잘되어 있어서 참고하면 이해가 잘 된다.

소수의 정의가 1과 자기 자신이외의 나눠지는 수가 없다는 것인데, 소수의 배수는 소수가 아니다.
ex) 2의 2배는 2x2가되어서 4가된다. 4의 약수는 1,2,4이므로 소수가 아니다.

100 아래의 수 중에 소수를 구하라고 했을때 우리는 100의 제곱근인 10의 배수까지 반복을 해주면된다.

WHY?
소수가 아닌 수는 합성수이다. 합성수는 약수들의 곱으로 이루어져있는데 일반식은 "A x B= 합성수"이다.
이때 합성수가 100이라면 100의 제곱근은 10이다. 제곱근으로 합성수를 만들기 위해서 "10 x 10 = 100"이라는 식이 나온다.

A의 값이 작아지면 자동으로 B의 값이 커진다. 즉 A의 값은 10보다 작아지지만 B의 값은 10보다 커진다.
"10 x 10 =100" == "2 x 50 = 100" == "4 x 25 == 100"

A와 B의 자리를 바꾸어도 같다.
"50 x 2 = 100" == "25 x 4 == 100

2에서 50을 곱하는것과 50에서 2를 곱하는건 중복된다. 따라서 합성수의 제곱근까지 구하는 것이 불필요한 반복을 줄이기 때문이다.

코드로 구현해보자

---

2. 소수 구하기 [시간복잡도 O(nlog * logn)]

int n = 100;
bool[] primes = new bool[n + 1];

for (int i = 2; i <= n; i++)
{
    primes[i] = true;
}

for (int i = 2; i <= Math.Sqrt(n); i++)
{
    if (primes[i])
    {
        for (int j = i+i; j <= n; j += i)
        {
            primes[j] = false;
        }
    }
}

for (int i = 2; i <= n; i++)
{
    if (primes[i])
    {
        Console.Write(i + " ");
    }
}

이 코드에서 두번째 반복문인 for (int j = i+i; j <= n; j += i)를 최적화 한다면 for (int j = i*i; j <= n; j += i) 가 된다.

WHY?
예를들어 i가 3이면 j의 초기화 값은 6이다.
6은 i가 2일때 이미 false처리가 되었으므로 i*i인 9부터 시작해도된다.

i가 4일때면 j의 초기화 값은 8이다.
8은 i가 2일때 이미 false처리가 되고 j의 다음값인 12는 i가 3일때 false처리가 된다.
즉 i*i인 16부터 시작해도된다.

에라토스테네스의 체 알고리즘을 사용한 백준 알고리즘 제출 코드는 아래와 같다.

---

3. 소수 구하기 [시간복잡도 O(nlog * logn)] - 백준 제출 최적화 코드

using System.Text;

StringBuilder sb = new StringBuilder();
int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

bool[] nums = new bool[input[1] + 1];

for (int i = 0; i <= input[1]; i++)
{
    nums[i] = true;
}

for (int i = 2; i <= Math.Sqrt(input[1]); i++)
{
    if (nums[i] == true)
    {
        for (int j = i * i; j <= input[1]; j += i)
        {
            nums[j] = false;
        }
    }
}

for (int i = 2; i <= input[1]; i++)
{
    if (nums[i] == true && i >= input[0])
        sb.AppendLine(i.ToString());
}

Console.WriteLine(sb.ToString());