자바 약수 갯수 구하기 실행시간 단축

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

약수의 갯수

자기 자신을 나누어서 떨어지는 수를 의미하고 이들의 갯수의 합이 약수의 갯수이다. 16의 경우 1, 2, 4, 8, 16 이므로 5이고 9의 경우 1, 3, 9이므로 약수의 갯수는 3이다

자바 약수 갯수 구하기 버전 1

가장 기본적으로 자바의 약수의 갯수를 구할 때 2중 반복문을 사용하면 쉽게 구할 수 있다.

1~100,000까지 모든 약수의 갯수를 구해보자!!! 약수를 효율적으로 구하는 방법은 자바 약수 구하기 포스트 참조

int n = 10,000

for(int i=1 ; i<=n ; i++) {
  int cnt = 0

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

  print("i 의 약수의 갯수는 : " + cnt)
}

숫자가 커질수록 반복하는 횟수가 점차 증가합니다. 효율적인 방법을 통해 실행시간을 줄여야겠죠?

자바 약수 갯수 구하기 버전 2

이전 포스트인 자바 소수 구하기에서 배수를 활용하여 합성수를 체크하는 방법을 사용했었습니다. 마찬가지로 약수의 갯수를 구할 때 배수의 개념과 배열을 활용하면 효율적으로 약수의 갯수를 체크할 수 있습니다.

int n = 10,000
int [] count = new int[n + 1]

for(int i=1 ; i<=100 ; i++) {
  for(int j=1 ; j<=100 ; j++) {
    count[i*j]++
  }
}

위의 반복문을 실행하면 1-1, 1-2, 1-3, 1-4 … 1-100, 2-1, … 2-100, 100-100 이 됩니다. i x j = 숫자가 되고 그 숫자의 약수를 하나씩 더해가는 개념입니다. 약수 갯수 구하기 1의 방법이 1+2x2+3x3+….10000x10000 번의 수행결과가 필요하다면 2번의 방법은 100x100의 사이즈만큼의 수행만 필요한 것을 알 수 있습니다.