약수 찾는 알고리즘

어떤수 N 의 약수를 구하기위해선 어떻게 해야할까?

N을 N보다 작은 모든수로 다 나눠보면 된다.

10의 경우

10/1

10/2

10/3

10/4

10/5

10/6

10/7

10/8

10/9

10/10

식으로 나눈 후 나머지가 0인 수들을 10의 약수로 칭할 수 있다.

코드로 쓰면 아래와 같다.

for(int i=0; i<=10; i++){
	if(10%i==0){System.out.println(i+"는 10의 약수입니다.");}
    	else{System.out.println(i+"는 10의 약수가 아임다.");}
}

시간복잡도는 O(n)이다.  1개의 for문에 비례한다.

 

두번째 방법은 

N 의 약수들을 생각해보자,

10의경우 우선 a x b 의 꼴로 생각해 볼 수 있는데,

2x5, 1x10 으로 생각해볼 수 있다. 이때 10의 절반인 5보다 작은 수는 1과 2이고 5보다 크거나 같은 수는 5와 10이다.

즉 어떤수 N 을 axb 의 형태로 생각했을 때(a<b) a를 검사하면 b는 자동적으로 나오는 느낌이다.

(10 일 경우 1~4, 1~(10/2-1) 까지만 검사해보면 10의 약수들을 찾을 수 있다.)

코드로 써보자,

for(int i=0; i<5;i++){
	if(10%i==0){System.out.println(i+"와"+10/i+"는 10의 약수입니다.");}
}

 

for문의 길이가 절반으로 줄어든다. 

조금더 시간을 단축 할 방법은 없을 까?

다른 수 16을 가지고 생각해보자,

16의 경우 약수가 {1, 2, 4, 8, 16}이다. 

4x4에 대해 생각해 볼 수있는데, 4는 루트16이다.

다시 말해 어떤수 N을 axb의 형태로 생각해 보았을 때(a<b) a의 최댓값은 sqrt(N)보다 작거나 같음을 알 수 있다.

36의 경우 6일것이고, 49의 경우 7, 그리고 36~49 사이의 수의 경우 6.xxx 보다 작거나 같을것이다.

 

우리는 이를통해 어떤수 N 의 약수를 검사할때 for문을 sqrt(N) 까지만 검사해보면 됨을 알 수 있다.

코드를 짜보자.

 

public class Aug_10 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        double sqrt = Math.sqrt(N);

        int cnt = 0;

        for(int i=1;i <= sqrt;i++){
            if(N%i==0){
                System.out.println(i+"와"+N/i+"는 "+N+"의 약수입니다.");
                cnt++;
            }
        }

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

이런식으로 반복문을 N회에서 sqrt(N)회로 줄였다.

따라서 O(sqrt(N)) 이다. 

 

시간을 많이 줄일 수 있다.