[인프런] 소수 (에라토스테네스 체) - 자바

알고리즘 문제를 풀다 보면 반드시 나오는 주제
바로 소수찾기다.

이번에 푼 문제는 정수가 하나 주어지면 1부터 그 수 사이에 있는 소수의 개수를 찾는 문제다.

처음 시도한 풀이

처음에는 이중 for문을 이용하여 숫자 하나하나를 살펴보면서 소수인지 아닌지 판단하는 식으로 구현했다.

결과는 역시나 시간초과...

public static int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        boolean flag = true;
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            answer++;
        }
    }
    return answer;
}

 

에라토스테네스 체

고대 그리스 수학자 에라토스테네스가 만들어 낸 소수 찾는 방법이라고 한다.

에라토스테네스의 소수 찾는 방식

1부터 20 사이의 수 중에서 소수를 찾는다고 하면,

 

1은 소수가 아니므로 처음부터 지운다.

2의 배수를 모두 지운다.
3의 배수를 모두 지운다.
4는 이미 지웠으므로 패스한다.
5의 배수를 모두 지운다.

6은 이미 지웠으므로 패스한다.

...

 

이러한 방식으로 20까지 진행하는 것이다.

 

에라토스테네스 체에 대한 이론 설명을 듣고 다시 코드를 짜 봤다.

public static int solution(int n) {
    int answer = 0;
    int[] numbers = new int[n + 1]; // 생성할 때 0으로 초기화된다. 
    for (int i = 2; i < numbers.length; i++) {
        if (numbers[i] == 0) {
            answer++;
            for (int j = i; j < numbers.length; j++) {
                if (j % i == 0) {
                    numbers[j] = 1;
                }
            }
        }
    }
    return answer;
}

그런데 또 시간초과ㅜㅜ

안쪽 for문에서 j가 모든 숫자를 돌면서 그 수가 i의 배수인지를 하나하나 따져보는 코드였다.

이렇게 하면 처음 짠 코드랑 별 다를 바가 없다.

 

정답 풀이

public static int solution(int n) {
    int answer = 0;
    int[] numbers = new int[n + 1]; // 생성할 때 0으로 초기화된다. 
    for (int i = 2; i < numbers.length; i++) {
        if (numbers[i] == 0) {
            answer++;
            for (int j = i; j < numbers.length; j = j + i) {
                numbers[j] = 1;
            }
        }
    }
    return answer;
}

안쪽 for문에서 j++이 아닌 j = j+i 라고 하는 것이 문제 해결의 키였다.

이렇게 하면 j가 i의 배수인지 확인하는 조건문 없이 i의 배수를 모두 지울 수 있다.