알고리즘. 에라토스테네스의 체. 소수 구하기. 자바

 

문제

 

숫자 n이 주어질 때, n보다 작거나 같은 수 중에서 소수가 몇개 있는지 출력하기

소수란, 1과 자기 자신으로 밖에 나누어지지 않는 수로 

예를 들어서 2,3,5 ... 등이 있다.

4의 경우 1과 2 그리고 4로 나누어지므로 소수가 아니다.

 

 

난이도

 

하

 

설명

 

1. n이 주어지므로 n 크기 공간의 배열을 생성한다.

2. 그리고 모든 배열을 0으로 초기화 한다. 

3. 배열에 해당하는 값이 아닌 배열의 인덱스를 각각의 숫자로 가정할 때 1번 인덱스는 소수가 아니므로 건너뛰고 2번 인덱스는 소수이므로 count 를 1 증가 시키고, 2의 배수에 해당하는 숫자는 자기 자신과 1 말고도 2로 나누어지므로 소수가 아니다. 따라서 계산에서 제외하기 위해 내부 값을 1로 변경한다.

4. 위와 같은 방법으로 숫자를 점차 늘려 나가며 계산한다.

 

계산하는 과정은 아래와 같다.

 

 

 

풀이

 

public int solution(int n) {
    int count = 0;

    // n+1 크기 만큼 생성 1부터 n까지의 인덱스로 접근할 수 있음
    int[] nums = new int[n+1];

    // 2 번 인덱스부터
    for (int i=2; i<nums.length; i++) {

        // 1이면 이미 제외된 숫자
        if (nums[i] == 0) {
            count++;
            for (int j = i; j<nums.length; j+=i) {
                // i의 배수가 1이 아닐 경우만 1로 변경
                if (nums[j] != 1) {
                    nums[j] = 1;
                }
            }
        }
    }


    return count;
}

깃허브 : github.com/donghyeon0725/algorithm_java/blob/master/src/com/inflearn/two/Five.java

 

 

 

문제점

 

위 방법을 사용하면 쉽고 빠르게 소수를 판별할 수 있지만, 하나 문제가 있다. 주어진 소수가 여러개인 경우이다.

이럴 경우 소수 하나마다 계속 새로운 배열을 생성해야 하므로, 이 또한 연산 속도에 많은 영향을 미친다.

이를 해결할 방법이 없을까?

 

당신도 나와 같은 생각을 하고 있는가!

맞다! 

자바에서는 static 키워드를 지원하고 있다.

이는 프로그램이 실행 될 때 메모리에 계속 올려두는 저장 공간이다.

이를 이용해서 미리 저장공간에 소수인지 아닌지 여부를 저장해두고 그 여부만 판별해서 꺼내 쓰면 된다.

 

 

방법

 

만약 판별해야할 소수를 n이라고 하고 n의 범위를 3 <= n <= 1000 이라고 가정하자 (2는 이미 소수임을 알고 있다).

 

그러면 우리는 길이가 1001인 배열 저장 공간이 필요하다. 0번은 사용하지 않을 것이기 때문이다(위 풀이 참고)

 

그리고 2이면 소수 1이면 소수가 아닌 것으로 가정하고 0이면 초기값이므로 탐색 전이라고 가정하겠습니다. 

그럼 아래와 같이 풀이할 수 있습니다.

 

public class Test {

    // 기본 0으로 초기화 되어 있다. 0은 아직 탐색 전, 1은 소수가 아님(탐색은 마침). 2는 소수
    private static int[] arr = new int[1001];

    // 인스턴스를 초기화 하고 싶을 때는 그냥 괄호 열면 되지만, static 필드를 초기화 하고 싶은 경우에는 static 키워드를 사용해야 한다.
    static {
        // 1은 소수가 아님
        arr[1] = 1;
        // 2는 소수
        arr[2] = 2;


        int total = 1000;
        // 3부터 탐색 => 2는 이미 소수인 것을 안다.
        for (int i=3; i<=total; i++) {

            // 지금 탐색하려는 대상이 아직 0 이면 소수임 => 체에 걸러지지 않은 값임
            if (arr[i] == 0) {
                arr[i] = 2;
            }

            // 배수 모두 1로 만듬
            for (int target = i; target<=total; target += i) {
                // 탐색 전인 것만 탐색 => 소수의 2배수 3배수... 배수인 값은 전부 소수가 아님. 예를 들어 2는 소수이나 4는 소수가 아님
                if (arr[target] == 0) {
                    arr[target] = 1;
                }
            }
        }

    }

    public static String solution(int[] a) {
        List<Integer> result = new ArrayList<>();

        for (int target : a) {

            if (isPrimeNumber(target)) {
                result.add(target);
            }

        }


        return Arrays.toString(result.toArray());
    }

    // 소수인지 판별
    public static boolean isPrimeNumber(int t) {
        if (arr[t] == 2) {
            return true;
        } else {
            return false;
        }
    }


    public static void main(String[] args) {
        int[] input = {32,55,62,20,250,370,200,30,100,23,2};
        System.out.println(solution(input)); // [23, 2]
    }
}