[ BOJ/C# ] 1929 소수 구하기 _ 에라토스테네스의 체

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

이번에는 n이하의 소수를 구하는 문제였기 때문에 에라토스테네스의 체를 이용하였다. 

에라토스테네스의 체를 이해한 개념을 바탕으로 간단히 말하자면, 

 

1) 우선 n까지의 각 수를 넣은 n크기의 배열을 만든다. 

2) 이 배열을 앞에서부터 시작하여,  현재 타겟 수의 값을 0으로 만든다.

3) 이를 n까지 반복하면 소수만 남는다. 

 

(2부터 시작하여 4, 6, 8...2n모두 0으로 만든다, 다음 3에서는 값이 0이 아닌 9, 15, 21... 3n을 0으로 만든다. )

이 방식을 사용하여 빠르게 n까지의 소수를 구할 수 있다. 

시간 복잡도는 O(N^1/2)라고 한다. 

using System;
using System.Text;

namespace B1929
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();

            int[] mn = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            if (mn[0] == 1) mn[0]++;

            //m이상 n이하 소수 배열 가져오기
            int[] prime = GetPrime(mn[0], mn[1]);
            for(int i = mn[0]; i < mn[1] + 1; i++)
            {
                if (prime[i] == 0) continue;
                sb.AppendLine(prime[i].ToString());
            }
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }

        static int[] GetPrime(int m, int n)
        {
            int[] array = new int[n + 1];

            for (int i = 2; i < n + 1; i++) array[i] = i;   //n까지의 수 넣기
            //약수 지우기
            for(int i = 2; i < n + 1; i++)
            {
                if (array[i] == 0) continue;
                //본인의 배수를 다 0으로
                for (int j = i + i; j < n + 1; j += i) array[j] = 0;
            }
            return array;
        }
    }
}

*틀렸습니다

한번 틀렸는데, 아래 반례를 기반으로 고쳤다. 반복문에서 한 부분이 n+1이 아닌 n으로 되어있었다. 

반례 

input :1 2

output:2