[Java] 소수의 판별 (최적화)

Minuuu·2023년 1월 15일

알고리즘

목록 보기

2/36

목적

소수 알고리즘을 이해할 수 있는 글 작성
성능 최적화(가지치기)를 고려한 글 작성

1. 소수란?

1과 자기자신만을 약수로 가지는 수 ex) 2, 3, 5, 7, 9
1은 소수가 아니다

2. 소수 알고리즘 접근방식

1 = 소수가 아님 => 약수 1개
2 = 소수 맞음 => 약수 2개
3 = 소수 맞음 => 약수 2개
4 = 소수 아님 => 약수 3개

"아! 약수의 갯수를 카운트해서 알고리즘을 구할 수 있겠구나!!"로 접근이 가능

public static boolean isPrime(int N) // O(N)의 시간복잡도
	{
		int count = 0; // N의 모든 약수의 갯수
		for(int i = 1; i <= N; i++){ // i = 1 ~ N사이의 모든 정수가 차례로 한 번씩 전부 
			if(N % i == 0){
				// i = 1 ~ N 사이의 모든 약수가 차례로 한 번씩 전부
				count++;
			}
		}
		return count == 2
	}

위의 접근 방식으로 코드를 짜면 이렇게 되고 O(N)의 시간 복잡도를 가진다
이를 가지치기를 통해 조금 더 개선해보자

3. 소수 가지치기 접근

어떤 수 N은 1과 자기자신만을 가져야 소수가 된다
짝수는 늘 2라는 약수를 가지게 된다 -> 4 이상의 짝수는 소수가 아니다
이를 적용시켜보자

public static boolean isPrime(int N) // O(N) but 짝수에는 O(1)
	{
		// 가지치기를 이용한 성능 개선
		if(N == 1) return false;
		if(N == 2) return true;
		else if(N % 2 == 0) return false;
		
		int count = 0; // N의 모든 약수의 갯수
		for(int i = 1; i <= N; i++){ // i = 1 ~ N사이의 모든 정수
			if(N % i == 0){
				// i = 1 ~ N 사이의 모든 약수가 차례로 한 번씩 전부
				count++;
			}
		}
		return count == 2
	}

이 코드의 시간복잡도는 O(N)이지만 짝수에 한해서 상수 시간[O(1)]이 돌아간다
하지만 그렇다고해도 최악의 경우(홀수) 아직도 O(N)을 가진다
자연수가 1이상 10억 이하의 자연수라고 가정한다면
시간복잡도에 10억을 대입하면 연산량은 수십억에 해당할 것이다
몇억 단위를 넘어가면 1~2초를 넘어가기 어렵다(시간 초과)
이를 더욱 더 개선해보자

4. 수학적 접근을 통한 가지치기

소수와 약수라는 수학적 성질을 이용해 크게 시간을 단축시킬 수 있다
자연수 N의 약수 a를 생각하고 N을 a로 나눈 몫을 구하면

N=ab(단, a\leq b)

즉, 자연수 N에 대해 서로 곱하여 N이되는 약수 쌍 a, b가 항상 존재한다
편의상 a <= b의 상황에만 고려하자

N = a * b(a \leq b)

위 조건에서 a가 가장 커질 수 있을 때는 a == b이다(a <= b 이기 때문)

N = a * a --> N = a^2 --> a = \sqrt N

즉 a = 루트 n일 때 최댓값을 가진다
그러므로, N이 소수가 아니라면(p) $2\leq a \leq \sqrt N$ 범위에 약수 a가 반드시 존재(q)

대우명제

$2\leq a \leq \sqrt N$ 범위에 약수가 없으면(~q) N은 소수다(~p)

어차피 우린 1,N이라는 약수가 있는 것을 알고 있으니
2 ~ N - 1범위에 약수가 하나라도 있으면 소수가 아니고 하나도 없으면 소수다

[2, $\sqrt N$ ]의 범위만 약수의 존재 여부를 검사하면 소수, 합성수를 구분 가능

소수 알고리즘은 많이 사용되니 이를 꼭 알아두자

최종소스코드

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
    * 주어진 숫자가 소수인지 판별하는 함수 
    *
    * @param N 
    * @return true   소수라면 
    * @return false  소수가 아니라면
    */
	public static boolean isPrime(int N) // O(N) but 짝수에는 O(1)
	{
		// 가지치기를 이용한 성능 개선
		if(N == 1) return false;
		if(N == 2) return true;
		else if(N % 2 == 0) return false;
		
		int count = 0; // 1, N을 미리 고려
		// 어차피 2까지는 소수니 3부터 고려하고 홀수 약수만 고려하기 위해 i+=2
		for(int i = 3; i <= Math.sqrt(N); i+=2){ // i = 1 ~ N사이의 모든 정수가 차례로 한 번씩 전부 
			if(N % i == 0){
				count++;
				break; // 하나라도 있으면 약수가 존재하는거니 바로 종료한다
			}
		}
		// count = [2, sqrt(N)]의 모든 약수의 개수
		return count == 0
	}

	public static void testCase(int caseIndex)
	{
		int n = scanner.nextInt();
		boolean result = isPrime(n);

		System.out.printf("Case #%d\n", caseIndex);
		if(result)
		{
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}

}

후기

문제에서 직접적으로 조건을 줘 시간 단축시키는게 아닌
이렇게 소수라는 데이터의 성질을 활용해 시간 단축하는 것을 배웠고
이를 잘 활용하기 위해선 알고리즘에서 자주 사용되는 소수 같은 데이터의 성질을
잘 학습 시켜야된다고 생각했다
다들 이 글을 꼭 이해해서 모두가 잘 적용했으면 좋겠다 :)