자바(Java)로 소수 판별하기 – 소수 확인 및 다음 소수를 찾는 프로그램

소수(prime number)란 1보다 큰 자연수 중에서 약수가 오직 1과 자기 자신뿐인 수를 말합니다. 즉, 이 두 숫자 외에는 양의 약수를 가지지 않습니다. 예를 들어 7은 1 × 7로만 표현할 수 있으므로 소수입니다.

소수 판별 알고리즘

어떤 수가 소수인지 아닌지 확인하는 기본적인 알고리즘은 다음과 같습니다.

• 정수 변수 A에 검사할 숫자를 저장합니다.
• A를 2부터 A-1까지의 값으로 나누어 봅니다.
• 이 범위 내의 어떤 값으로도 나누어 떨어진다면 A는 소수가 아닙니다.
• 나누어 떨어지는 값이 하나도 없다면 A는 소수입니다.

예제 코드

아래 자바 프로그램은 사용자로부터 정수를 입력받아 해당 숫자가 소수인지 판별하고, 이어서 그 다음으로 큰 소수를 찾아 출력합니다.

import java.util.Scanner;
public class NextNumberisPrime {
    public static int isPrime(int num){
        int prime = 1;
        for(int i = 2; i < num; i++) {
            if((num % i) == 0) {
                prime = 0;
            }
        }
        return num;
    }
    public static int nextPrime(int num) {
        num++;
        for (int i = 2; i < num; i++) {
            if(num%i == 0) {
                num++;
                i=2;
            } else {
                continue;
            }
        }
        return num;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number ::");
        int num = sc.nextInt();
        int result = 0;
        int prime = isPrime(num);
        if (prime == 1) {
            System.out.println(num+" is a prime number");
        } else {
            System.out.println(num+" is not a prime number");
        }
        System.out.println("Next prime number is: "+nextPrime(num));
    }
}

코드 설명

isPrime() 메서드는 2부터 입력값 미만까지 반복하며 나누어 떨어지는 경우가 있는지 검사합니다. nextPrime() 메서드는 입력값을 1씩 증가시키면서 다시 소수 여부를 검사하여, 가장 가까운 다음 소수를 반환합니다.

실행 결과

Enter a number ::
25
25 is not a prime number
Next prime number is: 29

위 실행 결과에서 볼 수 있듯이, 25는 5 × 5로 나누어 떨어지므로 소수가 아니며, 25보다 큰 가장 가까운 소수인 29가 출력됩니다.