기본 수학 2단계 1929

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

 

코드 참고

https://replit.com/@wny0320

wny0320 (박 상운)

 

1929번에 대해 다룸

 

---

1929

using System;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int[] Input= Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        List<bool> NotPrime = new List<bool>(new bool[Input[1] + 1]);
        NotPrime[1] = true;
        for (int i = 2; i * i <= Input[1]; i++)
        {
            if(NotPrime[i] == false)
            {
                for(int j = i+i; j <= Input[1]; j += i)
                {
                    NotPrime[j] = true;
                }
            }
        }
        if (Input[1] == 4)
        {
            NotPrime[2] = false;
            NotPrime[4] = true;
        }
        for (int i = Input[0]; i <= Input[1]; i++)
        {
            if(NotPrime[i] == false)
            {
                Console.Write(i + "\n");
            }
        }
    }
}

시간제한이 빡빡해서 에라토스테네스의 체를 이용하여 풀은 문제

 

0~Input[1] 즉 n에 해당하는 수까지 List<bool>을 생성

 

List<bool>(new bool[Input[1] + 1])을 통하여 기본값 false로 리스트를 채움

 

1은 소수가 아니므로 NotPrime[1] = true

 

다음은 에라토스테네스의 체로 거름

에라토스테네스의 체에 대한 내용

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Sieve of Eratosthenes - Wikipedia

이후 n이 4라면 반복문을 넘어가기 때문에 2를 소수로, 4를 소수가 아니게 설정