[C#] 백준 1929번 : 에라토스테네스의 체 방식(빠르게 소수 찾기)

using System;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        StringBuilder sb = new StringBuilder();
        string[] s = Console.ReadLine().Split();
        int M = int.Parse(s[0]);
        int N = int.Parse(s[1]);
        bool OK = true;

        if (M == 1) M++;
        for (int i = M; i < N; i++)
        {
            OK = true;
            for (int j = 2; j <= i; j++)
            {
                if (i != j && i % j == 0)
                {
                    OK = false;
                    break;
                }
            }
            if (OK)
                sb.AppendLine(i.ToString());
        }

        Console.Write(sb);
    }
}

 

이렇게 했는데 안됐다... 에라토스테네스의 체 방식을 사용해야한다고 한다. 그게 뭔지 몰라서 찾아봤다.

 

using System;

class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split();
        int M = int.Parse(s[0]);
        int N = int.Parse(s[1]);

        bool[] arr = new bool[N + 1];

        for (int i = 2; i < N + 1; i++)
            arr[i] = true;

        for (int i = 2; i <= N; i++)
        {
            if (arr[i])
            {
                for (int j = i * 2; j <= N; j += i)
                    arr[j] = false;
            }
        }
        for (int i = M; i <= N; i++)
            if (arr[i])
                Console.WriteLine(i);
    }
}

 

소수를 찾아 그 수의 배수는 모두 소수가 아니라는 처리를 해주는 방식이었다. 근데 이 답으로 해도 문제는 오답이었다...

 

using System;
using System.Text;

class Program
{
    static void Main()
    {
        StringBuilder sb = new StringBuilder();
        string[] s = Console.ReadLine().Split();
        int N = int.Parse(s[0]);
        int M = int.Parse(s[1]);
        
        bool OK = true;
        if (N == 1)
        n++;
        
        for (int i = N; i <= M; i++)
        {
            OK = true;
            for (int j = 2; j * j <= i; j++)
            {
                if (i != j && i % j == 0)
                {
                    OK = false;
                    break;
                }
            }
            if (OK)
            {
                sb.AppendLine(i.ToString());
            }
        }
        Console.Write(sb);
    }
}

 

구글링한 이 답은 또 정답이다... 처음이랑 뭐가 다른지...