프로그래머스 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

---

시간 초과 때문에 정말 힘들었다.
여러 시도를 해보며 시간을 뚫어보려 했지만 결국 이건 소수의 정의에 대한 수학적 개념이 필요하다 판단하고,
위키피디아를 참고했다.

참고하기 전까지 나의 전략이 에라토스테네스의 체와 동일하다는 것을 알 수 있었다.

3부터 주어진 숫자까지의 홀수 배열을 생성하고,
그 배열을 순회하며 소수를 만날 때마다 카운팅하고 그 수의 배수를 배열에서 제거하는 식이었다.
머릿속으로만 생각했을 때는 이게 가장 효율적일 것 같았다.
그리고 그 과정에서 List의 removeIf(e -> e % primeNumber == 0) 와 같은 식도 처음 사용해봤다.
설계 직후엔 아주 아름다워보였다.

그러나 배열 전체를 순회하며 조건을 검증하고, 특히 그 큰 배열에서 특정 요소를 제거하는 작업은
정말 많은 시간을 발생시키는 작업이었다.

게다가 3과 5처럼 작은 소수에서는 배열에서 그 배수를 제거하는 것이
많은 수를 제거하기 때문에 효율적인 것처럼 보였지만, 뒤로 갈수록 그렇지 않았다.

소수가 커질수록 그 배수를 제거하기 위해 들여야 하는 리소스에 비해,
그로 인해 작아지는 배열의 크기로 인한 효용이 감소했다. 아주 극단적으로 말이다.
뒤로 갈수록 점점 더 오래 걸리는 냄새나는 코드였다.

내가 모르고 있는 소수의 특성이나 정의에 대한 부분을 최대한 생각해내려 애써봤지만
안되겠다 싶어 찾아본 위키피디아에서 결국 결정적 힌트를 얻었다.

 

어떤 자연수 n이 소수임을 판정하기 위해선,
n제곱근까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다.

 

내가 기존에 사용하던 소수 판별식은 이랬다.
3부터 주어진 수까지의 홀수를 모두 대입하여 나눠서 몫이 0인지 확인하기.

그런데 만약 100을 판별한다면, 
100까지 나눠보는 게 아니라 10까지만 나눠보면 되는 것이었다.
(짝수니 당연히 판별할 필요가 없고 짝수로 나누는 것도 개념 오류이지만 쉽게 생각해보기 위해..)

왜냐하면 제곱근 자연수가 존재한다면, 그 수로 나누어진다는 의미이기 때문이다.

그래서 아래와 같이 판별식을 수정했다.

    public static boolean isPrimeNumber(int target) {
        boolean result = true;

        for (int i = 3; i <= Math.sqrt(target); i += 2) {
            if(target % i == 0) {
                result = false;
                break;
            }
        }

        return result;
    }

 

기존에 사용하던 것과 크게 달라진 점은 없으나 i의 최대 제한이 < target 에서 제곱근으로 바뀌었다.

이는 오히려 숫자가 커질수록 더 크게 탐색범위를 줄여준다.

수학 참... 쩝쓰.

힌트를  참고하긴 했지만... 어쨋든 풀어냈다!! 아하하 ;ㅅ;

 

다음은 최종 코드다.

package programmers.level1.소수찾기;

// 소수 찾기
// https://programmers.co.kr/learn/courses/30/lessons/12921

public class SearchPrimeNumber {

    public static void main(String[] args) {
        System.out.println(solution(10));
        System.out.println(solution(5));
        System.out.println(solution(1000000));
    }

    public static int solution(int n) {
        int result = 1;

        for (int i = 3; i <= n; i += 2) {
            if(isPrimeNumber(i)) result++;
        }

        return result;
    }

    public static boolean isPrimeNumber(int target) {
        boolean result = true;

        for (int i = 3; i <= Math.sqrt(target); i += 2) {
            if(target % i == 0) {
                result = false;
                break;
            }
        }

        return result;
    }
}