🌱 약수 개수 구하기

• 일반적인 방법

public class Solution {

    public void solution(int number) {
        long beforeTime = System.currentTimeMillis();

        int cnt = 0;
        for (int i = 1; i <= number; i++) {
            if (number % i == 0) cnt++;
        }

        System.out.println("약수의 개수 : " + cnt);

        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(ms) : " + secDiffTime);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.solution(123456789));
    }

}
//결과
약수의 개수 : 12
시간차이(ms) : 810

• 개선된 알고리즘

public class Solution {

    public int solution(int number) {
        long beforeTime = System.currentTimeMillis();

        int cnt = 0;
        for (int i = 1; i * i <= number; i++) {
            if (i * i == number) cnt++;
            else if (number % i == 0) cnt += 2;
        }

        System.out.println("약수의 개수 : " + cnt);

        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(ms) : " + secDiffTime);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.solution(123456789));
    }

}
//결과
약수의 개수 : 12
시간차이(ms) : 18

한 개의 약수를 찾는 순간, 반대편 약수의 존재도 보장된 것이므로 체킹 횟수를 대폭 줄일 수 있다.

Reference URL : https://devmoony.tistory.com/169