Java로 숫자가 소수인지 판별하는 프로그램 작성 방법

소수란 무엇일까요?

이 글에서는 Java를 사용해 숫자가 소수(prime number)인지 아닌지 판별하는 방법을 단계별로 알아보겠습니다. 소수는 1과 자기 자신이라는 두 개의 약수만을 가지며, 다른 어떤 수로도 나누어 떨어지지 않는 특별한 수입니다. 예를 들어 11의 약수는 1과 11 자신뿐이므로 소수입니다. 대표적인 소수로는 2, 3, 5, 7, 11, 13 등이 있으며, 2는 유일한 짝수 소수라는 점도 흥미롭습니다. 그 외의 모든 소수는 홀수입니다.

다음은 프로그램 실행 결과에 대한 간단한 시연입니다.

입력

사용자가 입력한 값이 다음과 같다고 가정해 보겠습니다.

Enter the number : 47

출력

원하는 출력 결과는 다음과 같습니다.

The number 47 is a prime number.

알고리즘

Step 1 - 시작
Step 2 - 정수형 변수 my_input을 선언한다.
Step 3 - 사용자로부터 값을 입력받거나, 값을 미리 정의한다.
Step 4 - for 반복문을 사용해 2부터 해당 숫자의 절반까지 범위에서 나누어 떨어지는 수가 있는지 확인한다. 나누어 떨어지는 수가 없으면 소수이고, 하나라도 있으면 소수가 아니다.
Step 5 - 결과를 화면에 출력한다.
Step 6 - 종료

예제 1 - 사용자 입력으로 소수 판별하기

첫 번째 예제는 Scanner 클래스를 사용해 사용자로부터 직접 숫자를 입력받은 뒤, 해당 숫자가 소수인지 판별합니다.

import java.util.Scanner;
public class IsPrime {
   public static void main(String[] args) {
      int my_input;
      System.out.println("Required packages have been imported");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("A reader object has been defined");
      System.out.print("Enter the number : ");
      my_input = my_scanner.nextInt();
      boolean isPrime = true;
      for (int i = 2; i <= my_input / 2; ++i) {
         if (my_input % i == 0) {
            isPrime = false;
            break;
         }
      }
      if (isPrime)
         System.out.println("The number " + my_input + " is a prime number.");
      else
         System.out.println("The number " + my_input + " is not a prime number.");
   }
}

출력 결과

Required packages have been imported
A reader object has been defined
Enter the number : 47
The number 47 is a prime number.

예제 2 - 미리 정의된 값으로 소수 판별하기

두 번째 예제는 입력값을 코드 안에 직접 정의한 뒤, 그 값의 소수 여부를 콘솔에 출력합니다.

public class IsPrime {
   public static void main(String[] args) {
      int my_input = 47;
      System.out.println("The number is defined as " + my_input);
      boolean isPrime = true;
      for (int i = 2; i <= my_input / 2; ++i) {
         if (my_input % i == 0) {
            isPrime = false;
            break;
         }
      }
      if (isPrime)
         System.out.println("The number " + my_input + " is a prime number.");
      else
         System.out.println("The number " + my_input + " is not a prime number.");
   }
}

출력 결과

The number is defined as 47
The number 47 is a prime number.

코드 동작 원리

두 예제의 핵심 로직은 동일합니다. 먼저 불리언 변수 isPrime을 true로 초기화한 뒤, for 반복문으로 2부터 입력값의 절반(my_input / 2)까지 차례대로 나누어 봅니다. 이 범위까지만 검사해도 충분한 이유는, 자기 자신과 1을 제외한 n의 가장 큰 약수는 반드시 n/2 이하이기 때문입니다. 만약 my_input % i의 나머지가 0, 즉 나누어 떨어지는 수가 발견되면 isPrime을 false로 바꾸고 break 문으로 반복문을 즉시 종료해 불필요한 연산을 줄입니다. 마지막으로 isPrime의 값에 따라 소수 여부를 출력합니다.

참고 사항

현재 알고리즘의 시간 복잡도는 O(n/2)이며, 검사 범위를 √n까지만 줄이면 성능을 훨씬 더 개선할 수 있습니다.
이 코드는 0, 1 또는 음수에 대해서는 소수로 잘못 판별할 수 있으므로, 실무에서는 2 미만의 값에 대한 예외 처리를 추가하는 것이 좋습니다.
Scanner 사용이 끝난 후에는 my_scanner.close()를 호출해 리소스를 해제하는 습관을 들이면 좋습니다.