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

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

• 문제

---

• 문제풀이

기본적으로 에라토스테네스의 체를 활용하는데 문제에서 N보다 크고 2N보다 작거나 같은 소수의 개수를 구하라고 했다. 처음에 N부터 시작해서 몇번 틀렸었다.

 

[알고리즘] 에라토스테네스의 체

---

• 코드 1

using System.IO.Pipes;
using System.Text;

namespace ConsoleApp7
{
    internal class Program
    {
        public static int count;
        public static StringBuilder sb = new StringBuilder();

        static void CalcPrime(int N)
        {
            int num = N * 2;
            int[] temp = new int[num + 1];
            for (int i = 2; i <= num; i++)
            {
                temp[i] = i;
            }
            for (int i = 2; i <= num; i++)
            {
                if (temp[i] == 0) continue;
                for (int j = i + i; j <= num; j += i)
                {
                    temp[j] = 0;
                }
            }
            
            for (int i = N+1; i <= num; i++)
            {
                if (temp[i] != 0)
                {
                    count++;
                    //sb.Append(temp[i] + " "); 소수 확인용

                }
            }
            sb.Append(count+"\n");
        }
        static void Main(string[] args)
        {
            while(true)
            {
                int N=int.Parse(Console.ReadLine());
                if (N == 1)
                {
                    sb.Append("1\n");
                }
                else if (N == 0)
                {
                    break;
                }
                else
                {
                    count = 0;
                    CalcPrime(N);
                }
            }
           
            Console.WriteLine(sb.ToString());

        }
    }
}

 

---

• 후기

문제를 잘 읽자