[ 완전탐색 연습문제 ] 프로그래머스 소수찾기 - 자바 Java

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

 

소수 란

우선 소수란 무엇인지 알아봅니다.  소수는 '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수'입니다.

2	3	5	7
1	1	1	1
2	3	5	7

2, 3, 5, 7의 경우를 보면 자신의 수 이외에 나누어지는 수는 1밖에 없습니다.

이처럼 어떤 수를 나누었을 때 나머지가 0인 수를 그 수의 '약수'라 합니다.

​위 숫자들은 1과 자기 자신 외에는 약수를 가지지 않는 수이므로 '소수'입니다.

 

에스토스테네스의 체 란

에라토스테네스의 체는 지정된 한계까지 모든 소수를 찾기 위한 고대 알고리즘입니다. 그것은 기원전 200년경 그리스 수학자 에라토스테네스에 의해 발명되습니다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다.

 

이 알고리즘은 발견된 각 소수의 배수를 2부터 시작하여 반복적으로 표시함으로써 작동합니다.  즉, 2의 배수인 모든 수, 3의 배수인 모든 수, 5의 배수인 모든 수를 지정된 수의 제곱근에 도달할 때까지 제거합니다.

 

예를 들어 숫자 30의 최대범위의 제곱근은 5이므로 5까지만 검사를 합니다. ( why? 5*5 <= 30 , 6*6 > 30 )

 

에스토스테네스의 체 자바 코드

import java.util.Arrays;
class Solution {
    public int solution(int n) {
        int answer = 0;
        int limit = n;
        
        boolean[] primes = new boolean[limit + 1]; 
        Arrays.fill(primes, true); // primes Array를 true로 세팅
        
        
        //첫번째 for문
        for (int p = 2; p * p <= limit; p++) {
            if (primes[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    primes[i] = false;
                }
            }
        }
        
        //두번째 for문
        for (int i = 2; i <= limit; i++) {
            if (primes[i]) {
                answer++;
                //System.out.print(i + " ");
            }
        }
        
        return answer;
    }
}

 

숫자 30의 범위에서 소수인 경우를 예시로 설명을 하겠습니다.

main 메서드은 크기 limit + 1 크기만큼 boolean prime Array를 초기화합니다. 즉, 배열은 0부터 시작하기 때문에 30의 소수를 구하기 위해서는 11 크기만큼 boolean primes 배열을 초기화합니다.(N번째의 수 까지 받기 위해 N+1까지 동적할당)

 

여기서 primes [i]가 소수이면 true이고 그렇지 않으면 false를 대입해 줍니다. 처음에는 primes의 모든 요소를 true로 설정합니다.

 

첫 번째 for문은 2부터 해당값(i)의 제곱근까지 모든 수를 확인합니다. 

초기에 p의 값은 2이므로 (primes [2])부터 시작을 합니다. 그래서 int i = p*p를 통해서 2를 제외한 2의 배수(4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30)를 모두 false로 만들어줍니다.

그다음으로 p는 3이 되므로 마찬가지로 3을 제외한 값( 9, 12, 15, 18, 21, 24, 27, 30 )을 false로 만들어줍니다.

그다음으로 p는 4가 되는데 4의 배수는 2의 배수를 체크할 때 모두 false로 만들어주어서 할 필요가 없습니다.

마지막으로 p의 값이 5가 있습니다. (왜 마지막?  p * p <= limit에서 p가 6인경우 p*p는 36이 되므로 limit값이 31이므로 for문에 조건에 해당되지 않기 때문입니다. 그렇기 때문에 p의 마지막값은 5가 됩니다.

 

두 번째 for문을 통해 소수를 출력합니다.

첫 번째 for문에 false가 되지 못한 값들은 모두 소수입니다. 즉, true 개수를 세어줍니다.

 

정리

1. 배열을 생성하여 true로 초기화해 줍니다.
2. 2부터 시작해서 제곱근의 값이 구하려는 수의 값보다 작거나 같은 경우에 false를 대입합니다. (자기 자신은 false를 대입하지 않고 true값만 찾아서 검사를 합니다)
3. 2부터 시작하여 true값만 모두 출력합니다.

---

에라토스테네스 구현 알고리즘(C언어)

C언어이지만 완전히 에라토스테네스의 체에 대해서 이해해 보시라고 링크를 남깁니다.

 

감사합니다.