[C# 문제] 소수 구하기

문제

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

단, 계산시간은 2초이내로 제한합니다.

 

입력

M과 N을 입력합니다. M과 N 사이에는 빈칸이 존재합니다.

 

출력

한 줄에 소수 하나씩 출력합니다.

 

힌트

에라토스테네스의 체 알고리즘을 사용해야 합니다.

반응형

코드

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            //M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

            string[] mn = Console.ReadLine().Split();

            Stopwatch t = new Stopwatch();//값을 입력받은 후 시간 체크

            t.Start();

            int m = int.Parse(mn[0]);
            int n = int.Parse(mn[1]);

            Dictionary<int, bool> primeNumber = new Dictionary<int, bool>();
            
            for(int i = 1; i <= n; i++)
            {
                bool isPrime = true;

                if (i == 1)//1은 소수가 아니다.
                    isPrime = false;
                else if (i > 2 && i % 2 == 0)//2보다 큰 짝수는 소수가 아니다.
                    isPrime = false;

                primeNumber.Add(i, isPrime);
            }

            for (int i = 3; i <= n; i += 2)//홀수만 체크
            {
                for (int j = i * 2; j <= n; j += i)
                {
                    if(primeNumber[i])//i가 소수면 
                    {
                        primeNumber[j] = false;//소수의 배수는 소수가 아니다.
                    }
                }
            }

            StringBuilder sb = new StringBuilder();

            for(int i = m; i <= n; i ++)
            {
                if (primeNumber[i])
                {
                    sb.Append(i);

                    if (i < n)
                        sb.Append("\n");
                }
            }

            Console.WriteLine(sb);

            t.Stop();

            Console.WriteLine(t.Elapsed);
        }
    }
}

 

결과