효율적으로 약수 구하기 - O(√N)

SEPTEMBER·2025년 1월 8일

오늘은 효율적으로 약수를 구하는 방법에 대해 알아보겠습니다. 먼저 기본적인 방법으로 약수를 구해보고, 이후에 좀 더 효율적인 방법으로 접근하여 약수를 구하고 시간 복잡도를 줄이는 과정을 보여드리겠습니다.

기본적인 약수 구하는 방법

어떤 수 𝑁의 약수를 구하는 가장 기본적인 방법은 1부터 𝑁까지 모든 수를 나누어 나머지가 0이 되는 수를 찾는 것입니다. 아래 코드와 같이 1부터 𝑁까지 루프를 돌면 쉽게 결과를 도출할 수 있습니다.

  // O(N) 방식 - 비효율적
  for (int i = 1; i <= N; i++) {
      if (N % i == 0) {
          System.out.println(i);
      }
  }

시간 복잡도: 𝑂(𝑁)

하지만 이와 같은 방법은 모든 수를 검사해야 하므로 큰 수일수록 실행 시간이 오래 걸리며, 앞으로 설명드릴 방법보다 효율적이지 않습니다.

효율적으로 약수 구하는 방법

약수는 항상 '쌍'으로 존재한다는 사실을 알면, 어떤 수 𝑁의 약수를 구하기 위해 1부터 √N 까지 수만 나누어 떨어지는지 확인하면 되기 때문에 보다 효율적으로 약수를 구할 수 있습니다. 또한 입력 크기가 커질수록 기존 𝑂(𝑁) 방식보다 훨씬 빠르게 결과를 도출할 수 있습니다.

	// O(√N) 방식 - 효율적
	for (int i = 1; i * i <= N; i++) {  // √N까지만 검사
        if (N % i == 0) {  // i가 약수라면
            System.out.println(i);  // 작은 약수 출력
            if (i != N / i) {  // 중복 방지 (제곱수인 경우)
                System.out.println((N / i));  // 대응하는 큰 약수 출력
            }
        }
    }