약수 개수 알고리즘(java 프로그래머스 억억단을 외우자)

약수 개수 알고리즘 효율적으로 만들기

(1)이전 알고리즘

public static void getDivisorArr(int e,int[] divisorArr){
    for(int i=1; i<=e;i++){
        divisorArr[i] = getDivisorNumber(i);
    }
}

public static int getDivisorNumber(int n){
    int count =0;
    double sqrt = Math.sqrt(n);
    if(sqrt%1==0){
        count++;
        if(n==1){
            return count;
        }
    }

    for(int i=1; i<sqrt;i++){
        if(n%i==0){
            count+=2;
        }
    }

    return count;
}

 

500만개 기준 시간:20004ms

 

(2)개선된 알고리즘

1. 홀수는 약수도 홀수만 가지는것을 이용

public static int getDivisorNumber2(int n){
    int count =0;
    double sqrt = Math.sqrt(n);
    if(sqrt%1==0){
        count++;
        if(n==1){
            return count;
        }
    }
    if(n%2==0){
        for(int i=1; i<sqrt;i++){
            if(n%i==0){
                count+=2;
            }
        }
    }else{
        for(int i=1; i<sqrt;i=i+2){
            if(n%i==0){
                count+=2;
            }
        }
    }
    return count;
}

500만개 기준 시간: 14979ms

 

2. 소인수분해를 이용한 약수 개수 알고리즘+홀수는 약수도 홀수만 가지는것을 이용

public static void getDivisorArr2(int e,int[] divisorNumber){
    List<Integer> primeList = new ArrayList<>();
    for(int i=1; i<=e;i++){
        if(divisorNumber[i]==0){
            divisorNumber[i] = getDivisorNumber2(i);
            primeList.add(i);
        }
        for (Integer prime : primeList) {
            if(i*prime<=e){
                if(divisorNumber[i*prime]!=0){
                    continue;
                }
                if(i%prime==0){
                    int num = i;
                    int count = 0;
                    while(num%prime==0){
                        num = num/prime;
                        count++;
                    }
                    divisorNumber[i * prime] = divisorNumber[i]/(count+1)*(count+2);
                }else{
                    divisorNumber[i * prime] = divisorNumber[i] * 2;
                }
            }else{
                break;
            }
        }
    }
}

500만개 기준 시간:867ms

 

3.소인수분해를 이용한 약수 개수 알고리즘+홀수는 약수도 홀수만 가지는것을 이용+소수는 약수개수가 2인것을 이용

public static void getDivisorArr3(int e,int[] divisorNumber){
    List<Integer> primeList = new ArrayList<>();
    divisorNumber[1] = 1;
    for(int i=2; i<=e;i++){
        if(divisorNumber[i]==0){
            divisorNumber[i] = 2;
            primeList.add(i);
        }
        for (Integer prime : primeList) {
            if(i*prime<=e){
                if(divisorNumber[i*prime]!=0){
                    continue;
                }
                if(i%prime==0){
                    int num = i;
                    int count = 0;
                    while(num%prime==0){
                        num = num/prime;
                        count++;
                    }
                    divisorNumber[i * prime] = divisorNumber[i]/(count+1)*(count+2);
                }else{
                    divisorNumber[i * prime] = divisorNumber[i] * 2;
                }
            }else{
                break;
            }
        }
    }
}

500만개 기준 시간:186ms

 

if(divisorNumber[i]==0){
    divisorNumber[i] = getDivisorNumber2(i);
    primeList.add(i);
}

 

특정 소수 미만의 숫자들은 특정소수보다 작은 소수들의 곱으로 이루어져있으므로 배열값이 0이면 무조건 소수이므로 약수의개수를 2로 해주고 소수리스트에 추가시켜준다.

 

 

 

if(i%prime==0){
    int num = i;
    int count = 0;
    while(num%prime==0){
        num = num/prime;
        count++;
    }
    divisorNumber[i * prime] = divisorNumber[i]/(count+1)*(count+2);
}else{
    divisorNumber[i * prime] = divisorNumber[i] * 2;
}

 

숫자 i가 소인수로 prime을 갖는 경우 소인수의 약수개수공식에 의하여 prime의 인수에 1을 더해 각각의 다른 남은 소수들의 인수에 곱해주면 i*prime 약수의 개수가 된다.

 

ex) i = 12 = 2^2*3^1  (약수의 개수=(2+1)*(1+1)=6)

      i*prime = 24 = 12*2 = 2^3*3^1(약수의 개수 =  12의 약수의 개수/(2+1)*(3+1))

 

숫자 i가 소인수로 prime을 갖지 않는 경우 소인수의 약수개수 공식에 의하여 i*prime의 약수의 개수는 i의 약수의 개수에 2배가 된다.

ex) i = 12 = 2^2*3^1  (약수의 개수=(2+1)*(1+1)=6)

     i*prime = 84 = 12*7 =2^2*3^1*7^1(약수의 개수 =(2+1)*(1+1)*(1+1)) 

 

4.배수를 활용한 알고리즘

public static void getDivisorArr4(int e,int[] divisorNumber){
    for(int i=1;i<=e;i++){
        for(int j=1; j<=e/i;j++){
            divisorNumber[i*j]++;
        }
    }
}

500만개 기준 시간:462ms

 

알고리즘 코드

https://github.com/yougeun6021/Algorithm/blob/master/src/Algorithm/PrimeNumber.java

GitHub - yougeun6021/Algorithm

 

프로그래머스 억억단을 외우자

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

 

https://github.com/yougeun6021/Algorithm/blob/master/src/Level3/Memorize.java

GitHub - yougeun6021/Algorithm