백준 C# - 1929 +) 에라토스테네스의 체

풀이

처음에 1978과 같은 형식으로 문제를 풀었는데 계속 시간초과가 나왔다.

백준 C# - 1978 +) 풀이

위의 방식대로하게 된다면 시간 복잡도는 O(N²)이다.

두 반복문에서의 모든 i에 대해 모든 j값으로 나눗셈을 진행하므로 N * N이므로 O(N²)이 된다.

 

시간초과가 뜬다.

---

에라토스테네스의 체를 사용해야 한다.

왜 사용해야하는가?

임의의 자연수 n에 대하여 그 이하의 소수를 찾는데 제일 효율적인 방법이다.

반복문을 사용하여 각 숫자의 배수를 제외시키기 때문에 중복 계산을 하지 않으므로 빠르게 동작한다. 

 

에라토스테네스의 체 알고리즘

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

1) 2부터 시작하여 범위 내의 모든 숫자를 대상으로 한다.

2) 2는 소수이므로 2의 배수를 모두 제외시킨다.

3) 2를 제외하고 남아 있는 숫자 중에서 가장 작

은 소수를 선택한다.

4) 선택된 그 배수를 모드 제외시킨다.

이러한 과정을 반복한다.

---

시간 복잡도

에라토스테네스의 체에서 특정 소수 p를 찾았을 때, 그 소수 p의 배수를 찾아내고 제거한다. 이 루프는 p²부터 시작하여 p, 2p, 3p, ... 순으로 모든 배수를 제거한다.
가장 많이 실행되는 경우는 n 이하 중 √n 이하의 가장 큰 소수 p이다. 왜냐하면 만약 √n 이상의 수가 있다면 이미 다른 소수에 의해 처리 되었을 것이다. 따라서, 가장 많이 실행되는 루프는 p에 대해 O(loglogn)번 반복된다. 이는 소수 p의 성질에 관련된 복잡도이다. 그리고 가장 많이 실행되는 루프의 작업량은 O(√n)이다. 이 루프는 p² 부터 시작하여 p, 2p, 3p, ... 순으로 배수를 제거한다. 

결론

에라토스테네스의 체의 전체 시간 복잡도는 모든 작은 소수에 대해 O(log log n)번 반복되는 작업이 발생하며 가장 많이 실행되는 루프는 p에 대해 O(loglogn)번 반복되고, 그 작업량은 O(√n)이므로 O(NloglogN)이 된다. 

---

코드 설명

01 max + 1 크기의 배열을 true로 초기화

bool[] isPrime = Enumerable.Repeat(true, max+1).ToArray();

 

02 에라토스테네스의 체 알고리즘 구현

for (int i = 2; i * i <= max; i++)
{
    if (isPrime[i])
    {
        // i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
        for (int j = i * i; j <= max; j += i)
        {
            isPrime[j] = false;
        }
    }
}

 

03 true인 것만 출력

for (int i = Math.Max(2, min); i <= max; i++)
{
    if (isPrime[i])
    {
        sb.AppendLine(i.ToString());
    }
}
Console.Write(sb.ToString());

---

코드 전문

using System;
using System.Linq;
using System.Text;

namespace baek2
{
    class Program
    {
        static void Main(string[] args)
        {
            string word = Console.ReadLine();
            string[] token = word.Split();
            int min = int.Parse(token[0]);
            int max = int.Parse(token[1]);

            StringBuilder sb = new StringBuilder();
            bool[] isPrime = Enumerable.Repeat(true, max+1).ToArray();

            for (int i = 2; i * i <= max; i++)
            {
                if (isPrime[i])
                {
                    for (int j = i * i; j <= max; j += i)
                    {
                        isPrime[j] = false;
                    }
                }
            }

            for (int i = Math.Max(2, min); i <= max; i++)
            {
                if (isPrime[i])
                {
                    sb.AppendLine(i.ToString());
                }
            }

            Console.Write(sb.ToString());
        }
    }
}