[프로그래머스/Lv.1] 소수 만들기(feat.에라토스테네스의 체) - Java

📌 문제

프로그래머스

📌 소수 판별하기

문제를 풀기 전에, 소수를 판별하는 알고리즘을 짜보자! 소수란 1과 자기 자신만을 약수로 가지는 수이다. 즉, 2부터 자기 자신 - 1 까지의 수 중에서 하나라도 약수가 존재한다면 그 숫자는 소수가 아니다.

 

이대로 코드를 짠다면 다음과 같이 짤 수 있을 것이다.

public static boolean isPrime(int n) {
    if (n < 2) return false;
    else {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

• n이 2보다 작다면
  • 소수가 아니므로 false를 반환한다.
• n이 2보다 크다면
  • 2부터 n - 1까지 돌면서 약수가 존재하면 false를 반환한다.
  • 약수가 존재하지 않으며 true를 반환한다.

해당 코드는 모든 경우의 수를 돌며 약수 여부를 확인하기 때문에 O(N)의 시간복잡도를 가진다. 여기서 시간복잡도를 줄이려면 모든 약수들은 대칭 형태를 이룬다는 것을 기억한다.

📌 제곱근 이용하기

예를 들어 16의 약수 1, 2, 4, 8, 16에서 1 * 16 = 16 * 1, 2 * 8 = 8 * 2 처럼 대칭을 이룬다. 즉 16의 제곱근인 4를 기점으로 대칭을 이룬다는 것이다. 그렇기 때문에 n의 제곱근까지만 약수의 여부를 검증해도 되고, 시간복잡도는 더 줄어든다. 아래 코드는 반복문을 제곱근까지만 돌도록 수정한 코드이다. 제곱근을 이용해 더 효율적인 소수 판별 함수를 만들었다. 이 경우의 시간복잡도는 O(√N)이다.

public static boolean isPrime(int n) {
    int end = (int) Math.sqrt(n);
    if (n < 2) return false;
    else {
        for (int i = 2; i <= end; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

 

만약 대량의 소수를 한꺼번에 판별하고자 한다면 에라토스테네스의 체를 이용해 효율적으로 판별할 수 있다.

📌 에라토스테네스의 체

에라토스테네스의 체 알고리즘은 소수를 판별할 범위만큼 배열을 만든 뒤, 인덱스에 해당하는 값을 넣어주고 하나씩 지워나가면서 소수만 남기는 알고리즘이다. 아래 애니메이션을 보면 이해가 될 것이다. 2의 배수부터 시작해 3의 배수, 4의 배수, 5의 배수...이렇게 차례대로 지워나가다보면 남는 숫자들이 소수이다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

위 애니메이션을 코드로 구현하면 다음과 같다. 

public static void primeNumerSieve() {
    int number = 120;
    int[] a = new int[121];

    for (int i = 2; i <= number; i++) {
        a[i] = i;
    }

    for (int i = 2; i <= number; i++) {
        if (a[i] == 0) continue;
        for (int j = i + i; j <= number; j += i) {
            a[j] = 0;
        }
    }

    for (int i = 2; i <= number; i++) {
        if (a[i] != 0) System.out.print(a[i] + "  ");
    }

}

•  int형 배열 a의 i번째 인덱스에 2부터 number까지 차례로 대입한다.
• 2부터 number까지 돌면서 i의 배수인 경우 0으로 초기화한다.(소수가 아닌 숫자를 지워가는 과정)
• 모두 지웠다면 다시 2부터 number까지 돌면서 a의 i번째 인덱스의 값이 0이 아닌 경우(소수인 경우) 출력한다.

이 과정을 거치면 1부터 25 사이의 소수를 모두 구할 수 있다. 훨씬 더 큰 수를 넣어도 간단하게 소수 판별이 가능하다.

에라토스테네스의 체 알고리즘은 O(Nlog(log N))의 시간복잡도를 가진다.

📌 풀이

제곱근을 이용한 풀이

먼저 3개의 수를 더한 값이 소수인지 판별하는 메서드 isPrime()을 만들었다. n이 2 미만일 경우는 소수가 아니므로 제외하고, 반복문으로 2부터 n의 제곱근까지 돌면서 약수가 존재한다면 제외한다. 약수가 존재하지 않는다면 answer(소수가 되는 경우의 개수)을 1 증가시킨다.

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

 

이 isPrime() 메서드를 이용해 nums에 있는 모든 숫자들을 하나씩 돌며 3개의 수의 합이 소수인지 확인한다.

int sum = 0;
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        for (int l = j + 1; l < nums.length; l++) {
            sum = nums[i] + nums[j] + nums[l];
            isPrime(sum);
        }
    }
}

에라토스테네스의 체를 이용한 풀이

에라토스테네스의 체를 이용해서도 풀 수 있다. 이번에는 boolean 값을 반환하는 primeNumberSieve() 메서드를 만들었다. boolean형 배열 a의 크기를 n + 1로 설정하고, 2미만인 a[0]과 a[1]은 소수가 아니므로 true로 설정했다.  2부터 n까지 돌면서 a[i]가 true가 아니라면 i의 배수만큼 돌며 소수가 아닌 수에 해당하는 인덱스에 true를 대입하였다.(boolean 배열을 생성하면 기본값이 false 이므로) 이렇게 하면 a[n]을 반환했을 때 false가 나와야 소수인 것이다.

public boolean primeNumberSieve(int n) {
    boolean[] a = new boolean[n + 1];
    a[0] = a[1] = true;
        
    for (int i = 2; i <= n; i++) {
        if (a[i] == true) continue;
        for (int j = i + i; j <= n; j += i) {
            a[j] = true;
        }
    }
        
    return a[n];
}

 

이 primeNumberSieve() 메서드를 이용해 nums에 있는 모든 숫자들을 하나씩 돌며 3개의 수의 합이 소수인지 확인한다. primeNumberSieve(sum)이 false여야 NOT 연산으로 true가 되어 answer가 1 증가한다.

int sum = 0;
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        for (int l = j + 1; l < nums.length; l++) {
            sum = nums[i] + nums[j] + nums[l];
            if (!primeNumberSieve(sum)) answer++;
        }
    }
}

 

두 방식의 속도 차이는 다음과 같다.

에라토스테네스의 체() / 제곱근(오) 

📌 전체 코드

class Solution {
    int answer = 0;
    public int solution(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int l = j + 1; l < nums.length; l++) {
                    sum = nums[i] + nums[j] + nums[l];
                    is_prime(sum);
                }
            }
        }

        return answer;
    }
    
    public void is_prime(int n) {
        if (n < 2) {
            return;
        }
        
        if (n == 2) answer++;
        
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return;
        }
        
        answer++;
    }
    
}

class Solution {
    int answer = 0;
    public int solution(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int l = j + 1; l < nums.length; l++) {
                    sum = nums[i] + nums[j] + nums[l];
                    if (!primeNumberSieve(sum)) answer++;
                }
            }
        }

        return answer;
    }
    
    public boolean primeNumberSieve(int n) {
        boolean[] a = new boolean[n + 1];
        a[0] = a[1] = true;
        
        for (int i = 2; i <= n; i++) {
            if (a[i] == true) continue;
            for (int j = i + i; j <= n; j += i) {
                a[j] = true;
            }
        }
        
        return a[n];
    }
    
}

 

참고

https://youtu.be/5ypkoEgFdH8?si=wNK6BQwQYbnvjA_E

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)