[C#] 2581번: 소수

목차

---

백준 단계별로 풀어보기

25.09.17

9단계: 약수, 배수와 소수 1

2581번: 소수

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

 

문제 풀이

>> 풀이

1. 두 자연수 M과 N을 각각 입력받아 int값으로 변환하고 소수의 합을 담을 변수 'sum'과 소수 중 최솟값을 담을 변수 'min'을 선언한다.
2. for 반복문을 M부터 N까지 반복하여 아래 과정을 실행한다.
   •     약수의 개수를 담을 변수 'factorCount'를 초기화한다.
   •     for 반복문을 1부터 i까지 반복하여 i를 j로 나눈 나머지가 0이라면 j가 i의 약수이므로 factorCount를 1 늘린다. 이때, factorCount가 2보다 크다면 i는 이미 소수가 아니므로 바로 for 반복문을 탈출하여 연산 과정을 줄인다.
   •     찾은 약수의 개수가 2개라면 i는 소수이므로 sum에 i를 더해준다. 이때, sum이 0이라면 i가 소수 중 최솟값이므로 min에 i를 대입한다. --> 현재 소수를 찾는 과정이 작은 수부터 시작하여 큰 수로 나아가기 때문
3. 모든 과정이 끝났을 때, min이 0이라면 소수가 없는 것이므로 '-1'을 출력하고, 아니라면 sum과 min을 각각 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        int M = int.Parse(Console.ReadLine());
        int N = int.Parse(Console.ReadLine());
        int sum = 0;
        int min = 0;

        for (int i = M; i <= N; i++)
        {
            int factorCount = 0;
            for (int j = 1; j <= i; j++)
            {
                if (factorCount > 2) break;
                
                if (i % j == 0)
                {
                    factorCount++;
                }
            }

            if (factorCount == 2)
            {
                if (sum == 0) min = i;
                sum += i;
            }
        }
        
        if (min == 0)
            Console.Write("-1");
        else
        {
            Console.WriteLine(sum);
            Console.Write(min);
        }
    }
}