소수 구하는 방법 (Java)

 

약수 알고리즘 (Java)

이전에 작성했던 약수 알고리즘을 바탕으로 설명할 것이다.

 

방법 1

 

소수는 1과 자기 자신만을 약수로 가지기 때문에 2부터 자기 자신 - 1까지 반복문을 돌면서 나누어 떨어지는 수가 없다면 소수이고, 나누어 떨어지는 수가 있다면 소수가 아니다.

 

boolean solution(int num) {
    // 1은 소수 x
    if (num == 1) {
        return false;
    }

    // 2부터 자기 자신-1까지 반복
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

시간복잡도는 O(N)이 된다.

 

방법 2

 

위에 첨부한 약수 알고리즘의 방법 2를 보면 1부터 √N까지 반복해도 되는 이유를 알 수 있다. (참고 바랍니다.)

boolean solution(int num) {
    if (num == 1) {
        return false;
    }

    for (int i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

한번 더 자세히 설명하자면, N이 16이라 가정하자.

16의 약수는 1, 2, 4이다.

이때 약수 1이 정해지면 4/1 = 4도 약수가 되고, 2가 정해지면 4/2 = 2가 약수가 되는 규칙을 알 수 있다.

따라서 시간 복잡도는 O(√N)이 되어 방법 1보다 효율적이다.

 

방법 3

 

에라토스테네스의 체를 이용한 방법이다.

이 방법은 소수를 찾는 방법으로 위의 약수 알고리즘에서 간략하게 설명했지만 여기서 좀 더 자세히 다루겠다.

마치 체를 거르는 것과 비슷하다고 하여 그렇게 이름이 지어졌다.

 

 

먼저 1은 소수가 아니므로 1을 제거한다.

2를 제외한 2의 배수를 제거한다.

3을 제외한 3의 배수를 제거한다.

4의 배수는 이미 2의 배수에서 제거되었으므로 통과한다.

... 

 

이 또한 방법 2를 적용시켜 범위의 최댓값의 제곱근까지만 반복하면 된다.

static void solution() {
    arr[1] = true;

    for (int i = 2; i <= Math.sqrt(maxN); i++) {
        if (arr[i]) {
            continue;
        }

        for (int j = i * i; j <= maxN; j += i) {
            arr[j] = true;
        }
    }
}

여기서 j의 범위를 i * i부터로 시작한 이유를 예시로 들어 살펴보자.

i가 4일 때, 정석대로라면 i * 2인 8부터 시작이지만 사실상 i * 2, i * 3은 이미 2와 3의 배수이므로 제거된 상태다.

따라서 i * i부터 시작해도 된다.

 

에라토스테네스의 체의 시간복잡도는 O(log(logN))이다.

 

 

추천 문제

1978번: 소수 찾기

 

Reference

https://st-lab.tistory.com/80

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4