이 글에서는 Java를 사용하여 1부터 N까지의 모든 소수(Prime Number)를 찾아 화면에 출력하는 방법을 알아봅니다.
먼저 기본 개념을 짚고 넘어가겠습니다. 1부터 무한대까지의 모든 양의 정수를 자연수라고 부릅니다. 그중에서 소수는 1과 자기 자신을 약수로만 가지는 특별한 수로, 다른 어떤 수로도 나누어 떨어지지 않습니다.
예를 들어 11은 소수입니다. 11의 약수는 1과 11뿐이기 때문입니다. 대표적인 소수로는 2, 3, 5, 7, 11, 13 등이 있습니다. 특히 2는 유일한 짝수 소수이며, 나머지 모든 소수는 홀수라는 점도 기억해 두면 좋습니다.
문제 예시
입력값으로 n = 10이 주어졌을 때, 기대하는 출력 결과는 다음과 같습니다.
입력: 10
출력: 2 3 5 7
알고리즘
소수를 판별하는 핵심 로직은 다음과 같은 순서로 진행됩니다.
- 프로그램을 시작합니다.
- 정수형 변수 n을 선언합니다.
- 사용자에게 정수 입력을 요청하거나, 값을 미리 지정(hardcode)합니다.
- 입력값을 읽어 들입니다.
- 2부터 n까지 반복하면서, 각 숫자 j가 1과 j 이외의 수로 나누어지는지 검사합니다.
- 나누어지는 수가 있으면 소수가 아니므로 다음 숫자로 넘어갑니다.
- 약수가 1과 자기 자신뿐이라면 해당 숫자를 소수로 저장합니다.
- 모든 소수를 화면에 출력합니다.
- 프로그램을 종료합니다.
예제 1: 사용자 입력으로 소수 구하기
다음 예제에서는 Scanner 클래스를 사용해 사용자로부터 직접 값을 입력받습니다.
import java.util.Scanner;
public class PrimeNumbers{
public static void main(String arg[]){
int i, n, counter, j;
Scanner scanner = new Scanner(System.in);
System.out.println("필요한 패키지가 임포트되었습니다");
System.out.println("Scanner 객체가 생성되었습니다");
System.out.print("n 값을 입력하세요 : ");
n = scanner.nextInt();
System.out.print("1부터 " + n + " 사이의 소수는 ");
for(j = 2; j <= n; j++){
counter = 0;
for(i = 1; i <= j; i++){
if(j % i == 0){
counter++;
}
}
if(counter == 2)
System.out.print(j + " ");
}
}
}실행 결과
필요한 패키지가 임포트되었습니다 Scanner 객체가 생성되었습니다 n 값을 입력하세요 : 10 1부터 10 사이의 소수는 2 3 5 7
예제 2: 값이 미리 정의된 경우
다음 예제에서는 입력값이 코드 안에 미리 정의되어 있으며, 실행 시 콘솔에 바로 결과가 출력됩니다.
public class PrimeNumbers{
public static void main(String arg[]){
int i, n, counter, j;
n = 10;
System.out.printf("n 값은 %d 입니다", n);
System.out.printf("\n1부터 %d 사이의 소수는 ", n);
for(j = 2; j <= n; j++){
counter = 0;
for(i = 1; i <= j; i++){
if(j % i == 0){
counter++;
}
}
if(counter == 2)
System.out.print(j + " ");
}
}
}실행 결과
n 값은 10 입니다 1부터 10 사이의 소수는 2 3 5 7
코드 동작 원리
두 예제 모두 이중 반복문을 활용합니다. 바깥쪽 반복문은 2부터 n까지의 각 숫자를 하나씩 확인하고, 안쪽 반복문은 해당 숫자를 1부터 자기 자신까지 차례대로 나누어 보며 약수의 개수를 셉니다.
약수의 개수(counter)가 정확히 2개(1과 자기 자신)라면 그 숫자는 소수이므로 출력합니다. 이 방식은 이해하기 쉬운 기본적인 소수 판별법으로, 학습용 예제에 적합합니다.
참고: 성능을 개선하려면 안쪽 반복문의 범위를 √j까지만 검사하거나, 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하면 훨씬 빠르게 소수를 구할 수 있습니다.