[이산수학][Java] 주어진 수 N의 약수 구하기 구현

주어진 수 N의 약수 구하기

1. 단순한 방법(비효율적)

• 약수의 개수를 구하고자 하는 N을 1 ~ N까지의 수 A로 나눈다.
• N이 A로 나누어 떨어지면 A는 N의 약수이다.
• 시간 복잡도 : O(N)

2. 최선의 방법

• 약수의 개수를 구하고자 하는 N을 1 ~ N의 제곱근까지의 수 A로 나눈다.
• N이 A로 나누어 떨어지면 A는 N의 약수이다.
• N을 A로 나눈 몫인 B도 N의 약수이다.
• 시간 복잡도 : O(√N)

3. 구현

[git 저장소에 저장된 소스 코드 링크 : 약수 구하기]

package math;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class FindDivisors {
	
	static int countDivisors(int num) {
		int count = 0;
		List<Integer> divisors = new ArrayList<>();
		
		// 1. 숫자 num의 제곱근까지의 수 중에 100을 그 수로 나누었을 때 나누어 떨어지는지 확인
		for(int i = 1; i <= Math.sqrt(num); i++) {
			if(num % i == 0) {
				divisors.add(i);
				count++;
				// 2. 그 수로 num을 나눈 수도 약수이다. 다만 같으면 한 번만 센다.
				if(i != (num / i)) {
					divisors.add((num / i));
					count++;
				}
			}
		}
			
		System.out.println(divisors);
		return count;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int num = scan.nextInt();
		int numberOfDivisors = countDivisors(num);
		System.out.println(numberOfDivisors);
	}
}