[Java] 소수 판별 함수(메소드) isPrime

isPrime 메소드

프로그래밍 언어를 학습하다보면 소수를 구해야하는 순간이 언젠가 찾아오게 된다. 

그렇다면 소수란 무엇일까?

소수(prime number)

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수. 즉, 1과 n 사이에 n을 나눌 수 있는 다른 수가 없다면 소수라는 것이다.

 

*참고로 소수가 아닌 수를 합성수라고 부른다!

isPrime 메소드의 자바 코드

public static int isPrime(int n) {
	for (int i = 2; i <= Math.sqrt(n); i++) {
		if (n % i == 0) return 0;
	}
	return 1;
}

 

Math.sqrt(n)

위 코드에서 의문이 들만한 부분은 Math.sqrt(n)일 것이다.

왜 이 코드가 소수를 판별할 수 있는지 알아보자!

 

일반적으로 우리가 소수를 구할 때는 2부터 n까지의 수를 순차적으로 나눠가며 n에 도달하기 전에 다른 수에서 나눈 나머지가 0이 되는 경우, 즉 n이 아닌데 나누어 떨어지게 하는 수가 존재하는 경우 소수가 아니라고 판별한다. 반대로 n에 도달하기 전까지 나머지가 계속 존재한다면 소수라고 판별하는 것이다. (당연한 소리)

 

하지만 이 방법대로 하게 되면 n의 크기가 커졌을 때의 효율이 엉망일 것이다. n이 1억이라면 1억까지 반복문이 돌아가야 한다는 것인데, 수가 더 커지면 커질수록 상당히 비효율적일 것이다.

 

그래서 Math.sqrt(n)를 사용하는 것이다. Math 클래스에 있는 sqrt() 메소드는 우리가 알고 있는 제곱근(루트, √ )를 의미한다.

√n을 다르게 표현하면 n^(1/2)인데, 만약 1억을 기준으로 놓고 본다면 10의 8제곱에서 10의 4제곱(1만)으로 횟수가 크게 줄어들게 되어 1억번 돌려야 하는 경우보다 훨씬 빠르다.

 

여기까지 읽었다면 "빠른건 알겠는데, 제곱근까지만 확인해서 소수인걸 알 수가 있나?" 하는 생각이 들 것이다. (맞췄쥬?)

이것은 간단하게 해소할 수 있는 내용이다. 

 

만약 n이 √n보다 큰 수로 나누어 떨어지는 상황이라면 이미 √n보다 작은 수에서 나누어 떨어졌어야 하는 것이기 때문에 제곱근까지만 확인해도 소수임을 확인할 수 있는 것이다. 즉 소수가 아닌 경우, √n을 기준으로 양쪽에 수들이 대칭을 이루고 있기 때문에 √n보다 작은 수까지만 확인해도 소수임을 판별할 수 있는 것이다.

 

 

+2023.09.21 내용 추가

❗️ isPrime 메소드를 작성할 때 주의할 점

내용을 추가하게 된 이유는 저의 무지를 기록하고, 같은 실수를 반복하지 않기 위해서 입니다!

 

아래 두 개의 isPrime 코드를 확인해보세요.

// 1번: i <= (int) Math.sqrt(num)
private boolean isPrime(long num) {
	if (num < 2) {
		return false;
	}
        
	for (int i = 2; i <= (int) Math.sqrt(num); i++) {
		if (num % i == 0) {
			return false;
		}
	}
        
	return true;
}

// 2번: i * i <= num
private boolean isPrime(long num) {
	if (num < 2) {
		return false;
	}
        
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0) {
			return false;
		}
	}
        
	return true;
}

 

아시겠지만 소수인지 판별하는 메소드입니다. 두 코드 모두 작은 숫자를 입력한다면 같은 결과를 반환합니다. 하지만 두 코드에서 보이는 for문의 조건은 큰 수를 다루는 경우 결과가 달라집니다.

 

이유를 설명 드리겠습니다.

i * i <= num
매 반복마다 i * i를 계산합니다. i * i가 int 범위를 초과하면 오버플로가 발생하여 부정확한 결과를 반환할 수 있습니다. 따라서, 매우 큰 i 값에 대해서는 정확한 비교를 할 수 없게 됩니다.

i <= (int) Math.sqrt(num)
반복문 시작 전에 한 번만 제곱근을 계산하고, 그 이후에는 i를 이 값과 비교합니다. Math.sqrt는 double 형 값을 반환하므로 (int)로 형 변환해야 합니다. 이 방법은 오버플로 문제를 해결하고, i * i를 매번 계산하는 것보다 효율적입니다.

코드를 자세히 보시면 메소드의 매개변수가 long 타입임을 알 수 있습니다. 수가 커지는 경우를 생각해서라도 Math.sqrt()를 사용하는 것이 바람직합니다.

 

❗️추가 - 반복횟수를 1/2로 줄이는 isPrime 메소드

// 소수 판별
private boolean isPrime(long num) {
    if (num < 2) {
        return false;
    }
    
    if (num == 2) {
        return true;
    }
    
    if (num % 2 == 0) {
        return false;
    }
    
    int sqrt = (int) Math.sqrt(num);
    for (int i = 3; i <= sqrt; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }
    
    return true;
}

소수 판별 로직에서 2의 배수는 먼저 걸러낼 수 있기 때문에 2만 예외로 처리한 후, 홀수로 나누어지는지만 확인하면 됩니다. 반복 횟수가 절반으로 줄어들고, 알고리즘이 좀 더 효율적으로 동작합니다.

---

의외로 간단한 소수 판별하기였습니다.

읽어주셔서 감사합니다.

 

+

간단하지 않았습니다.

깝치지 않겠습니다.