마른하늘에날벼락처럼내려치는코딩

정수 N의 약수의 개수를 구할 때 1부터 N까지 반복문을 통해서 약수를 구하는 게 아닌,

Math.sqrt(N) 함수를 사용하여 간단한 시간복잡도로 약수의 개수를 구할 수 있다.

정답 코드

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for(int i=left; i<=right; i++){
            if(i % Math.sqrt(i) != 0) answer += i;
            else answer -= i;
        }
        
        return answer;
    }
}

*** 결과 ***

정수 N % N의 제곱근 == 0일 경우 N의 약수는 홀수개 이며, 

정수 N % N의 제곱근 != 0일 경우 N의 약수는 짝수개 이다.

▼ 기존 작성 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2; i<=n; i++){
            int cnt = 0;
            for(int j=1; j<=i; j++){
                if(i % j == 0) cnt ++;
                if(cnt > 2) break;
            }
            if(cnt == 2) answer++;
        }

        return answer;
    }
}

위 코드로 실행하였을때, 코드 자체는 성공하였으나 시간복잡도가 높아 통과되지 않는 케이스가 발생하였다.

▼ 수정된 코드

import java.util.*;

class Solution {
    public int solution(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }

        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) {
                count++;
            }
        }

        return count;
    }
}

위 코드는 에라토스테네스의 체 알고리즘을 보고 작성한 코드이다.

해당 코드로 수정했을때 시간복잡도가 해결되어 모든 테스트 케이스에 통과할 수 있었다.

***************************************************************************************************************

에라토스테네스의 체 알고리즘 이란?

고대 그리스 수학자 에라토스테네스가 발견한 제곱근을 이용한 소수를 구하는 방법.

소수를 구하는 최적의 알고리즘이라고 합니다.

소수는 n의 배수가 아니고 입력받은 수를 그 수보다 작은 수들로 나누어서 떨어지면 소수가 아니다.

그러므로, 모두 나누어 볼 필요없이 n 제곱근 까지만 나누어서 떨어지면 소수가 아니다.

***************************************************************************************************************