문 제

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

입 력

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

3 16

출 력

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

3
5
7
11
13

코 드

• n 보다 큰 제곱수가 나오기 전까지만 반복하면 된다!

예를 들어 (n = 1,000,000) 이라면 sqrt(n) 값 1000까지만 체크를 하면 된다! ‘에라토스테네스의 체’의 효율성!

using System;
using static System.Console;
using System.Linq;
using System.Text;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int m = int.Parse(input[0].ToString());
            int n = int.Parse(input[1].ToString());

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

            for (int i = 2; i * i <= n; i++)
            {
                if(isPrime[i] == false)
                    continue;

                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }

            StringBuilder sb = new StringBuilder();
            for (int i = m; i <= n; i++)
            {
                if(isPrime[i])
                    sb.AppendLine(i.ToString());
            }

            WriteLine(sb.ToString());
        }
    }
}

비교코드 - 1

공 부