백준 C# 1929 문제 풀이

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

목차

1 설명

 

2 내 코드

 

3 문제 풀이 해석 내용

 

4 실행 결과

 

설명

백준 실버 3 문제 입니다.

 

 

내 코드

string w = Console.ReadLine();
string[] t = w.Split();
int min = int.Parse(t[0]);
int max = int.Parse(t[1]);

StringBuilder sb = new StringBuilder();
bool[] isPrime = Enumerable.Repeat(true, max + 1).ToArray();

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

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

Console.Write(sb.ToString());

문제 풀이 해석 내용

입력 받기

string w = Console.ReadLine();
string[] t = w.Split();
int min = int.Parse(t[0]);
int max = int.Parse(t[1]);

사용자로 부터 두 개의 정수 (min, max)를 입력받습니다.

이 범위 내에서 소수를 찾습니다.

 

 

StringBuilder 초기화

StringBuilder sb = new StringBuilder();

소수를 저장할 문자열을 효과적으로 구성하기 위해서 StringBuilder를 사용합니다.

 

 

소수 판별을 위한 배열 초기화

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

isPrime 배열을 생성합니다.

이 배열은 각 숫자가 소수인지를 나타냅니다.

처음에는 모든 수를 소수로 가정합니다.

배열의 크기는 max + 1로 했습니다.

 

 

알고리즘

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

알고리즘을 사용하여 소수를 찾습니다.

i는 2부터 시작하여 max의 제곱근까지 반복합니다.

isPrime[i]가 true일 경우 i 배수들을 소수가 아니라고 판별하고 나타냅니다.

 

 

소수 출력

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

입력된 범위 내에서 소수를 찾아 StringBuilder 에 추가합니다.

Math.Max를 사용하여 2이하의 숫자는 소수로 고려하지 않습니다.

0과 1은 소수가 아니기 때문입니다.

 

 

결과 출력

Console.Write(sb.ToString());

마지막으로 찾아낸 결과를 출력합니다.

 

 

실행 결과

실행 결과