[백준 BAEKJOON] 1929번 소수 구하기

문제

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

 

입력

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

 

출력

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

 

1929번: 소수 구하기

 

 

기존 풀이 코드

바로 시간 초과가 출력됨, 기존 방식으로는 해결이 불가능

에라토스테네스의 체를 사용해야지 문제가 원하는 시간복잡도에 맞출 수 있을거라고 찾음

 

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var list = PrimeGenerator(3, 16);
        foreach (var i in list)
        {
            Console.WriteLine(i);
        }
    }

    static IEnumerable<int> PrimeGenerator(int start, int end)
    {
        for (int i = start; i <= end; i++)
        {
            if (IsPrime(i))
            {
                yield return i;
            }
        }
    }

    static bool IsPrime(int n)
    {
        for (int i = 2; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}

 

 

풀이 코드

기존 풀이 + 에라토스테네스 + StringBuilder를 조합해서 풀이를 진행함

 

list를 이용해서 소수 값을 출력하려고 하니 시간 초과가 출력되어서 다른 글을 참고해서 StringBuilder로 담아서 출력하니 시간초과가 뜨지 않고 정상적으로 해결됨 (해당 부분은 공부가 더 필요해보임)

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        Int32.TryParse(input[0], out int start);
        Int32.TryParse(input[1], out int end);

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

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

        StringBuilder sb = new StringBuilder();

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

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

 

함께 읽으면 좋은 글

[프로그래머스 Programmers] 소수 찾기

 

참고 사이트

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