C#에서 소수(prime number)를 판별하는 방법은 크게 두 가지가 있습니다. 하나는 for 루프를 직접 사용하는 방법이고, 다른 하나는 판별 로직을 함수로 분리하는 방법입니다. 이 글에서는 두 방법을 예제 코드와 함께 자세히 살펴봅니다.
먼저 소수의 개념을 간단히 짚고 넘어가겠습니다. 소수란 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 말합니다. 예를 들어 7은 1과 7로만 나누어 떨어지므로 소수이지만, 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아닙니다.
방법 1: for 루프를 사용한 소수 판별
1부터 n까지의 숫자로 n을 차례대로 나누어 보고, 나누어 떨어지는 횟수를 셉니다. 약수의 개수가 정확히 2개(1과 자기 자신)라면 그 수는 소수입니다.
using System;
namespace Program {
class Demo {
public static void Main() {
int n = 7;
int a = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
a++;
}
}
if (a == 2) {
Console.WriteLine("소수입니다");
} else {
Console.WriteLine("소수가 아닙니다");
}
}
}
}실행 결과
소수입니다
위 코드에서 변수 a는 약수의 개수를 저장하는 역할을 합니다. 7의 경우 1과 7로만 나누어 떨어지므로 a의 값이 2가 되고, 따라서 "소수입니다"가 출력됩니다. 만약 n이 6이라면 약수가 4개이므로 "소수가 아닙니다"가 출력됩니다.
방법 2: 함수를 사용한 소수 판별
판별 로직을 별도의 함수로 분리하면 코드의 재사용성과 가독성이 크게 향상됩니다. 아래 예제에서는 primeFunc() 함수가 소수 여부를 판단하여 그 결과를 반환합니다.
using System;
namespace Program {
class Demo {
static void Main(string[] args) {
int n = 7;
int res = primeFunc(n);
if (res == 0) {
Console.WriteLine("소수가 아닙니다");
} else {
Console.WriteLine("소수입니다");
}
}
private static int primeFunc(int n) {
int i;
for (i = 2; i <= n - 1; i++) {
if (n % i == 0) {
return 0; // 나누어 떨어지면 소수가 아님
}
}
if (i == n) {
return 1; // 소수임
}
return 0;
}
}
}실행 결과
소수입니다
primeFunc() 함수는 2부터 n-1까지의 수로 n을 나누어 보고, 하나라도 나누어 떨어지면 즉시 0(소수 아님)을 반환합니다. 반복문이 끝날 때까지 나누어 떨어지는 수가 없다면 1(소수)을 반환합니다. 이처럼 조건이 만족되는 순간 바로 반환하므로 불필요한 연산을 줄일 수 있습니다.
참고: 성능을 개선하는 팁
위 두 방법은 모든 후보 수를 검사하기 때문에 숫자가 커지면 비효율적일 수 있습니다. 실무에서는 다음과 같이 최적화하는 것이 좋습니다.
- 약수는 대칭적으로 존재하므로, 2부터 √n(제곱근)까지만 검사해도 충분합니다.
- n이 2 미만인 경우(0, 1, 음수)는 소수가 아니므로 반복문 전에 먼저 처리합니다.
- 2로 나누어 떨어지면 소수가 아니며, 이후에는 홀수만 검사하면 연산량을 절반으로 줄일 수 있습니다.
이러한 최적화를 적용하면 큰 수에 대해서도 훨씬 빠르게 소수 여부를 판별할 수 있습니다.