[Java] 약수 구하기 알고리즘

약수란?

---

어떤 수를 나누어 나머지가 없이 떨어지게 하는 수를 약수라고 합니다.

8을 1, 2, 4, 8 로 나누면 나누어떨어집니다.

이때 1, 2, 4, 8은 8의 약수입니다.

여러분 모두 아실거라 생각합니다.

 

Java로 약수를 구하는 알고리즘을 알아봅시다. 코딩 테스트에 종종 응용 문제로 출제됩니다.

 

약수 알고리즘

---

일반적 약수 알고리즘

int n = 100;

for(int i = 1; i <= n; i++){
	if(n % i == 0){
    	System.out.println(i + "는 약수 입니다.");
    }
}

• 가장 보편적으로 생각하는 약수를 구하는 코드입니다. 
• 만약 입력 값이 10000이라면 for 문을 입력 값 대로 실행해야 약수를 구할 수 있기 때문에 효율적이지 않습니다.
• 이 방법을 코딩 테스트에서 사용한다면 분명 런타임 에러가 발생할 것입니다.
  
  

최적화 알고리즘을 사용하기 위해서는 java.lang.Math 클래스의 sqrt() 메소드를 사용할 것 입니다.

그러므로 간단하게 알아봅시다.

 

java.lang.Math 의 sqrt() 메소드란?

---

sqrt() 메소드는 제곱근(root)을 구하는 함수이며 double 형으로 return 됩니다.

sqrt는 Square root를 의미합니다.

특징

• 인자로 a를 전달하면 a의 제곱근이 리턴됩니다.
• 인자로 0을 전달하면 0이 리턴됩니다.
• 인자로 음수나 NaN(Not a Number)를 전달하면 NaN이 리턴됩니다.

java.lang.Math 클래스는 수학 계산에 사용할 수 있는 메소드 들을 제공하고 있습니다.

Math 클래스 메소드들은 모두 static 메소드이므로 Import, 클래스 선언 없이 바로 사용 가능합니다.

double x = 25;
double y = 225;

System.out.println("Math.sqrt(x)=" + Math.sqrt(x));
System.out.println("Math.sqrt(y)=" + Math.sqrt(y));

//Output
//Math.sqrt(x)=5.0
//Math.sqrt(y)=15.0

 

sqrt 메소드를 사용한 최적화 약수 알고리즘

---

int n = 100; // 입력 값
int sqrt = (int) Math.sqrt(n); // 100의 제곱근은 10
ArrayList<Integer> arr = new ArrayList<>(); // 약수 받을 ArrayList

for(int i = 1; i <= sqrt; i++){
   if(n % i == 0){ // 약수 중 작은 수 저장
    arr.add(i);
        if(n / i != i){ // 약수 중 큰 수 저장
            arr.add(n / i);
        }
    }
}
// Java 8 이후 사용 가능
arr.sort(Comparator.naturalOrder());

System.out.println("오름차순 : " + arr);

• for 문 조건을 sqrt 메소드를 사용한 변수로 정의한다.
• 원래라면 1 ~ 100까지 돌아야할 for문이 1 ~ 10 까지만 돌아도 약수 추출이 가능해졌다.
• 입력 값 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 이렇게 9개이다.
• 10 번의 for 문을 돌며 9개의 약수 중 1을 구한다 (약수 중 작은 수)
• 1이 100의 약수라는 것을 알게 된 순간 100이라는 약수도 구할 수 있게 된다.
• 그 부분이 if(n / i != i) 부분이다. 100 / 1 != 1  이라면  arr 리스트에 100 / 1 의 값을 넣어준다(약수 중 큰수)
• 이 과정을 반복한다.
• 10 번의 for 문을 돌며 9개의 약수 중 2을 구한다 (약수 중 작은 수)
• 2이 100의 약수라는 것을 알게 된 순간 50이라는 약수도 구할 수 있게 된다.
• 그 부분이 if(n / i != i) 부분이다. 100 / 2 != 2  이면  arr 리스트에 100 / 2 의 값을 넣어준다(약수 중 큰수)
• 해당 부분은 약수 10을 주의 깊게 봐야한다 10 * 10이 100 이므로 10은 한번만 arr 리스트에 한번만 넣어야한다.
• 그 부분이 if(n / i != i) 부분이다. 100 / 10 != 10 false 이기 때문에 배열에 한번만 들어간다.
• for 문을 한번 돌 때 약수 중 작은 수 , 큰 수를 모두 arr 리스트에 넣기 때문에 for 문이 끝난 뒤 arr 리스트는
• 1, 100, 2, 50, 4, 25, 5, 20, 10 이런 식으로 값이 배열되어 있다.
• arr.sort()를 사용해 정렬을 진행한다.