C#으로 소수(Prime Number) 판별하기 – 초보자를 위한 완벽 예제

소수란 무엇인가?

소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 대표적인 예로 2, 3, 5, 7, 11, 13 등이 있으며, 프로그래밍 학습 과정에서 자주 다뤄지는 기본 알고리즘 주제 중 하나입니다.

소수 판별 알고리즘의 원리

숫자가 소수인지 확인하기 위해 이번 예제에서는 for 루프를 활용합니다. 루프의 매 반복마다 if 문으로 나머지가 0인지 검사하여, 해당 숫자의 약수 개수를 세는 방식입니다.

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

여기에 카운터 변수 a를 두었습니다. 만약 숫자가 소수라면, 이 카운터는 오직 두 번만 증가합니다. 바로 1로 나누어떨어질 때와 자기 자신으로 나누어떨어질 때입니다. 따라서 루프가 끝난 후 a의 값이 2라면 그 숫자는 소수라고 판단할 수 있습니다.

전체 예제 코드

아래는 C#에서 특정 숫자가 소수인지 확인하는 완전한 예제 코드입니다.

using System;
namespace Demo {
    class MyApplication {
        public static void Main() {
            int n = 5, a = 0;
            for (int i = 1; i <= n; i++) {
                if (n % i == 0) {
                    a++;
                }
            }
            if (a == 2) {
                Console.WriteLine("{0} is a Prime Number", n);
            } else {
                Console.WriteLine("Not a Prime Number");
            }
            Console.ReadLine();
        }
    }
}

실행 결과

위 코드를 실행하면 숫자 5는 1과 5로만 나누어떨어지므로 소수로 판별됩니다.

5 is a Prime Number

성능 개선 팁

위 방식은 1부터 n까지 모든 수를 검사하므로 직관적이지만, 숫자가 커지면 비효율적일 수 있습니다. 실무에서는 약수가 항상 쌍으로 존재한다는 성질을 이용해 √n(제곱근)까지만 검사하거나, 짝수를 미리 제외하는 등의 최적화 기법을 적용하면 실행 속도를 크게 향상시킬 수 있습니다.