[C#] 1929번: 소수 구하기

목차

---

백준 단계별로 풀어보기

25.11.10

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

1929번: 소수 구하기

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

 

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

>> 합성수의 특성

: 아래 글에 설명해두었다.

 

[C#] 4134번: 다음 소수

 

 

>> 소수 판별 함수 IsPrime()

: 합성수의 특성을 활용하여 효율적인 소수 판별 함수 IsPrime() 을 만들었다.

• num 이 1이라면 소수가 아니므로 false를 반환한다.
• num 이 2라면 소수이므로 true를 반환한다. --> 유일한 짝수 소수이다.
• num 이 짝수라면 소수일 수 없으므로 false를 반환한다.
• for 반복문을 효율적으로 사용하기 위해 Math.Sqrt 함수를 통해 num 의 제곱근을 limit 변수에 담는다.
• for 반복문을 통해 3부터 limit 까지 i 를 2씩 증가시키면서 num 을 i 로 나눈 나머지가 0이라면 소수가 아니므로 false를 반환한다.
• for 반복문을 빠져나왔다면 num 은 소수이므로 true를 반환한다. --> num 이 3, 5, 7 인 경우, limit 보다 i 가 작아서 자연스레 반복문을 빠져나오고 true를 반환한다. 

 

- 코드

// num > 0
private 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;
}

 

문제 풀이

: 만든 소수 판별 함수 IsPrime() 을 통해 소수를 찾아 출력한다.

1. StreamReader로 입력값을 받아 각각 int값으로 변환하여 자연수 M과 N을 담을 변수 m, n 에 담는다.
2. for 반복문을 통해 m 부터 n 까지 반복하며 만들어 둔 소수 판별 함수 IsPrime() 을 통해 i 가 소수인지 확인하고, 소수라면 StringBuilder에 담는다.
3. 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();
        
        string[] input = sr.ReadLine().Split();
        int m = int.Parse(input[0]);
        int n = int.Parse(input[1]);

        for (int i = m; i <= n; i++)
        {
            if (IsPrime(i))
            {
                sb.AppendLine(i.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;
    }
}