이 글에서는 하나의 숫자가 두 소수의 합으로 표현될 수 있는지 확인하는 방법을 자바 코드와 함께 살펴봅니다. 소수(prime number)란 1과 자기 자신이라는 두 개의 약수만을 가지며, 다른 어떤 수로도 나누어 떨어지지 않는 특별한 수를 의미합니다.
어떤 수의 약수가 오직 1과 자기 자신뿐이라면 그 수는 소수입니다. 예를 들어 11은 약수가 1과 11뿐이므로 소수에 해당합니다. 대표적인 소수로는 2, 3, 5, 7, 11, 13 등이 있으며, 참고로 2는 유일한 짝수 소수이고 나머지 모든 소수는 홀수입니다.
입력 및 출력 예시
입력
Input number : 43
출력
43 = 2 + 41
알고리즘
Step 1 - 시작 Step 2 - my_input과 i라는 두 개의 정수 변수를 선언한다 Step 3 - 사용자로부터 값을 입력받거나 값을 직접 정의한다 Step 4 - 정수값을 인자로 받아 해당 값이 소수인지 검사하는 IsPrime 함수를 정의한다 Step 5 - for 반복문을 사용해 2부터 my_input의 절반까지 순회하면서 i와 my_input - i가 모두 소수인지 확인하고, 조건을 만족하면 두 값을 저장한다 Step 6 - 결과를 출력한다 Step 7 - 종료한다
예제 1: 사용자 입력을 받는 경우
아래 예제에서는 Scanner를 통해 사용자가 직접 숫자를 입력하면, 해당 숫자가 두 소수의 합으로 표현되는지 확인하여 결과를 출력합니다.
import java.util.Scanner;
public class SumOfPrimes {
public static void main(String[] args) {
int my_input, i;
boolean my_temp = false;
my_input = 43;
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();
for (i = 2; i <= my_input / 2; ++i) {
if (IsPrime(i)) {
if (IsPrime(my_input - i)) {
System.out.println("The number can be expressed as sum of two prime numbers.");
System.out.println("The possible solutions are :");
System.out.printf("%d = %d + %d\n", my_input, i, my_input - i);
my_temp = true;
}
}
}
if (!my_temp)
System.out.println(my_input + " cannot be expressed as the sum of two prime numbers.");
}
static boolean IsPrime(int num) {
boolean my_prime = true;
for (int i = 2; i <= num / 2; ++i) {
if (num % i == 0) {
my_prime = false;
break;
}
}
return my_prime;
}
}실행 결과
Required packages have been imported A reader object has been defined Enter the number : 43 The number can be expressed as sum of two prime numbers. All the possible solutions are : 43 = 2 + 41
예제 2: 값이 미리 정의된 경우
아래 예제에서는 정수값이 코드 내에 미리 정의되어 있으며, 이 값을 콘솔에 출력하고 두 소수의 합으로 표현 가능한지 확인합니다.
public class SumOfPrimes {
public static void main(String[] args) {
int my_input, i;
boolean my_temp = false;
my_input = 43;
System.out.println("The number is defined as " +my_input);
for (i = 2; i <= my_input / 2; ++i) {
if (IsPrime(i)) {
if (IsPrime(my_input - i)) {
System.out.println("The number can be expressed as sum of two prime numbers.");
System.out.println("The possible solutions are :");
System.out.printf("%d = %d + %d\n", my_input, i, my_input - i);
my_temp = true;
}
}
}
if (!my_temp)
System.out.println(my_input + " cannot be expressed as the sum of two prime numbers.");
}
static boolean IsPrime(int num) {
boolean my_prime = true;
for (int i = 2; i <= num / 2; ++i) {
if (num % i == 0) {
my_prime = false;
break;
}
}
return my_prime;
}
}실행 결과
The number is defined as 43 The number can be expressed as sum of two prime numbers. All the possible solutions are : 43 = 2 + 41
코드 동작 원리 정리
핵심 로직은 크게 두 부분으로 나눌 수 있습니다.
1. 소수 판별(IsPrime) 함수: 2부터 해당 숫자의 절반까지 차례대로 나누어 보면서, 하나라도 나누어 떨어지면 소수가 아니라고 판단합니다. 나누어 떨어지는 수가 없다면 소수로 간주합니다.
2. 두 소수의 합 탐색: 2부터 입력값의 절반까지 반복하면서 'i'와 '입력값 - i'가 모두 소수인지 검사합니다. 두 값이 모두 소수라면 입력값은 두 소수의 합으로 표현할 수 있으며, 해당 조합을 출력합니다.
만약 끝까지 조건을 만족하는 조합을 찾지 못했다면, 해당 숫자는 두 소수의 합으로 표현될 수 없다는 메시지를 출력합니다.