[백준]4134, 1929, 4948, 17103

https://www.acmicpc.net/step/18

백준에서 소수와 관련된 문제들은 대부분 sqrt라는 제곱근과 관련된 내용으로 문제를 풀이한다.

나도 똑같이 문제를 풀고 해결하였으나 , 채점 현황중에 획기적으로 빠른 풀이가 있길래 갖고왔다.

아래의 풀이는 정말 빠르다. 핵심 아이디어는 "2와 3을 제외한 모든 소수는 6N± 1 이다." 라는 점이다.

    static boolean isPrime(int N) {
        if (N <= 1)
            return false;
        if (N <= 3)
            return true;
        if (N % 2 == 0 || N % 3 == 0)
            return false;
        int until = (int) Math.sqrt(N);
        // 소수의 배수면 그것 또한 탈락
        for (int i = 5; i <= until; i += 6) { //소수는 6의 배수+-1 이니까 6씩 점프
            if (N % i == 0 || N % (i + 2) == 0)
                return false;
        }
        // 앞에꺼 다 통과하면 소수맞다.
        return true;
    }

위의 메서드를 갖고서 문제를 풀어보니 기존 풀이보다 절반 정도 시간이 단축되었다.

실제로 종이에 풀 때 위 내용을 알고 나니 풀이가 굉장히 간단해진 것을 확인할 수 있다.

어디서 비슷한 문제를 풀거나 소수와 관련된 내용이 나오면 아는 척해보자.