약수란?
어떤 수를 나누어 나머지가 없이 떨어지게 하는 수를 약수라고 합니다.
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()를 사용해 정렬을 진행한다.