자바 약수 구하기 실행시간 단축 알고리즘 Java Divisor Algorithm

02 March 2020 - 2 mins read time
Tags: 자바 손코딩

약수란 ?

자기 자신을 나누어서 떨어지는 수를 의미한다. 16의 경우 1, 2, 4, 8, 16이 있고 9의 경우 1, 3, 9가 있다.

자바 약수 구하기 버전 1

자바의 약수를 구하는 방법은 반목문 1개와 조건문을 잘 활용하면 쉽게 구현이 가능하다

100의 약수를 구하는 방법으로 구해보자.

int n = 100

for(int i=1 ; i<=n ; i++) {
  if( n % i == 0 ) {
    print("i is 약수");
  }
}

100의 경우 1, 2, 4, 5, 10, 20, 25, 50, 100 이고 짝을 구해보면 1-100, 2-50, 4-25, 5-20, 10-10이 된다. 조금 변경을 한다면 효율적인 알고리즘 작성이 가능하다.

자바 약수 구하기 버전 2

n % i == 0 의 의미는 n/i 한 수와 i의 곱은 n 이다. 즉, 반복문의 과정을 반 이상 줄일 수 있다.

int n = 100

for(int i=1 ; i<=Math.sqrt(n) ; i++) {
  if( n % i == 0 ) {
    if( i*i == value ) print("i is 약수")
    else               print("i 와 n/i 도 약수") //100의 4와 25(100/4)
  }
}

Math.sqrt(100) = 10 을 활용하여 반복해야 하는 범위를 크게 줄일 수 있다. 약수를 구하기 위해 100번을 해야하는 로직을 10번 만으로 모든 약수를 구하고 알고리즘을 끝낼 수 있다.

스퀘어 함수를 사용하면 그 숫자는 n = 루트 n * 루트 n 으로 표시할 수 있다. 1 부터 루트 앤까지의 범위를 기준으로 해당 숫자를 나누고 떨어진다면 그 숫자가 약수가 되는 것을 알 수 있습니다. 100으로 따진다면 1 부터 10 까지가 왼쪽의 수 남은 오른쪽의 수는 100, 50, 25, 20, 10 이런식으로 표시된다고 생각하면 됩니다.