C#으로 숫자가 소수인지 확인하는 프로그램 작성 방법

소수(Prime Number)란 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수를 말합니다. 이 글에서는 C#의 반복문과 조건문을 활용하여 주어진 숫자가 소수인지 판별하는 프로그램을 작성하는 방법을 알아보겠습니다.

소수 판별의 기본 원리

핵심 아이디어는 간단합니다. 1부터 해당 숫자 n까지 차례대로 나누어 보면서, 나머지가 0이 되는 경우(즉, 약수를 찾은 경우)마다 카운터 값을 하나씩 증가시키는 것입니다.

for (int i = 1; i <= n; i++) {
    if (n % i == 0) {
        a++;
    }
}

여기서 카운터 변수 a는 숫자의 약수 개수를 세는 역할을 합니다. 어떤 수가 소수라면 그 약수는 1과 자기 자신 단 두 개뿐이므로, 루프가 끝난 후 a의 값이 정확히 2라면 그 숫자는 소수라고 판단할 수 있습니다.

전체 예제 코드

다음은 숫자 17이 소수인지 확인하는 완전한 C# 예제입니다.

using System;

namespace Demo {
    class MyApplication {
        public static void Main() {
            int n = 17, a = 0;

            // 1부터 n까지 나누어 약수 개수를 셉니다
            for (int i = 1; i <= n; i++) {
                if (n % i == 0) {
                    a++;
                }
            }

            if (a == 2) {
                Console.WriteLine("{0}: Prime Number", n);
            } else {
                Console.WriteLine("{0}: Not a Prime Number", n);
            }
            Console.ReadLine();
        }
    }
}

실행 결과

17: Prime Number

코드 설명

int n = 17 : 소수 여부를 확인할 대상 숫자입니다.
int a = 0 : 약수의 개수를 저장할 카운터 변수입니다.
for 루프 : 1부터 n까지 모든 숫자로 n을 나누어 나머지가 0인지 검사합니다.
if (a == 2) : 약수가 정확히 2개(1과 자기 자신)라면 소수로 출력하고, 그렇지 않으면 소수가 아니라고 출력합니다.

성능 개선 팁

위 방식은 1부터 n까지 모든 수를 검사하므로 시간 복잡도가 O(n)입니다. 숫자가 커지면 비효율적일 수 있으므로, 실제 프로젝트에서는 2부터 √n까지만 나누어 보는 방식으로 최적화하는 것이 좋습니다. 약수는 항상 쌍으로 존재하기 때문에 √n 이하에서 약수를 찾지 못했다면 그 이후에도 찾을 수 없기 때문입니다.