[C#] 4948번: 베르트랑 공준

목차

---

백준 단계별로 풀어보기

25.11.11

15단계: 약수, 배수와 소수 2

4948번: 베르트랑 공준

문제 링크 : https://www.acmicpc.net/problem/4948

 

문제를 풀기 위해 알아야 할 개념

>> 소수 판별 함수

: 아래 글에 정리해두었다.

 

소수 판별 함수 만들기

 

문제 풀이

: 만든 소수 판별 함수 IsPrime() 를 통해 

1. while 반복문을 활용하여 StreamReader로 입력값을 받아 int값으로 변환하여 변수 n 에 담고, 소수 개수를 담을 변수 result 를 0으로 초기화한다.
2. 입력값이 0이라면 반복문을 끝낸다.
3. n 보다 크고, 2n 보다 작거나 같은 소수의 개수를 구해야하므로 for 반복문을 활용하여 n + 1 부터 2n 까지 반복하면서 만든 IsPrime() 함수로 소수를 찾으면 result 를 1 증가시킨다.
4. 입력값 n 에 대하여 n 보다 크고, 2n 보다 작거나 같은 소수의 개수를 전부 찾았으면 그 result 값을 StringBuilder에 담는다.
5. while 반복문을 탈출하면 StreamWriter로 StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        while (true)
        {
            int n = int.Parse(sr.ReadLine());
            int result = 0;

            if (n == 0) break;
            
            for (int i = n + 1; i <= 2 * n; i++)
            {
                if (IsPrime(i))
                {
                    result++;
                }
            }

            sb.AppendLine(result.ToString());
        }
        
        sw.Write(sb.ToString());
    }

    static bool IsPrime(int num)
    {
        if (num == 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        int limit = (int)Math.Sqrt(num);

        for (int i = 3; i <= limit; i += 2)
        {
            if (num % i == 0) return false;
        }
        return true;
    }
}