기본 수학 2단계 4948

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

 

코드 참고

https://replit.com/@wny0320

wny0320 (박 상운)

 

4948에 대해 다룸

 

---

4948

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        List<int> Input = new List<int>();
        int cnt = -1;
        while(cnt == -1)
        {
            int buff = int.Parse(Console.ReadLine());
            if(buff == 0)
            {
                cnt = 0;
            }
            else
            {
                Input.Add(buff);
            }
        }
        int max = Input.Max();
        List<bool> NotPrime = new List<bool>(new bool[max * 2 + 1]);
        NotPrime[1] = true;
        for(int i = 2; i < max * 2; i++)
        {
            if(NotPrime[i] == false)
            {
                for(int j = i + i; j <= max * 2; j+=i)
                {
                    NotPrime[j] = true;
                }
            }
        }
        if(max == 2)
        {
            NotPrime[4] = true;
        }
        for(int i = 0; i < Input.Count; i++)
        {
            cnt = 0;
            for(int j = Input[i]+1; j <= Input[i] * 2; j++)
            {
                if(NotPrime[j] == false)
                {
                    cnt++;
                }
            }
            Console.WriteLine(cnt);
        }
    }
}

사실 앞의 문제인 소수 구하기 문제에서 문제점을 모두 찾아 해결해 어려운 것이 없었음

 

0이 입력될때까지 List에 값 추가 후 Linq를 이용하여 max값을 찾음

 

그리고 max 값의 2배 +1 크기의 bool 형 List를 생성

 

에라토스테네스의 체를 이용하여 max값의 2배되는 수까지 소수를 찾음

 

이후 n+1 ~ 2n사이의 값들에 대해 소수이면 cnt값을 증가시켜 출력을 반복함