약수 구하기 알고리즘

바다·2024년 5월 8일

Java TIL algorithm 코딩테스트

알고리즘 자료구조

목록 보기

3/4

손으로 푸는 건 쉽지만... 코드로 치는 건 그닥... 안 좋아했던 "약수 구하기"'

최근 코딩테스트 문제들 중에서 약수 를 구해야 풀 수 있는 문제들을 많이 접했고,
이 기회에 약수를 구하는 알고리즘을 정리해보아야겠다 싶어서 글을 작성한다!

약수

어떤 수를 나누어 나머지가 없게 떨어지게 하는 수

~~이걸 모르겠냐고~~~~ 다들 아시죠?
근데 이걸 코드로 구하라고 하니까 골치가 아픈 것임

1. 일반적인 방법

int num = 100;
int answer = 0;

for(int i = 1; i <= num; i++) {
	if(num % i == 0) answer++;
}

가장 기본적인 방법은 num을 1에서부터 num까지 나누면서, 나머지가 0인 경우를 세는 방식이다!

이 방식은 가장 기본적이지만, 숫자가 커질 경우 그만큼 for문을 돌아야하기 때문에 시간적으로 비효율적이다.. 😩

시간복잡도 = O(n)

2. 효율적인 방법

1) num의 제곱근 만큼만 for문을 돌기

int num = 100;
int answer = 0;

for(int i = 1; i*i <= num; i++) {
	if(i*i == num) answer++;			//i*i일 경우에는 한 개만 카운트
    else if(num % i == 0) answer += 2;	//아닐 경우에는 +2
}

예를 들어 num의 약수가 1이라면? 1이 num의 약수가 되도록 하는 1의 짝꿍도 있을 것이다!
이 짝꿍도 num의 약수이니 i*i가 num보다 작거나 같을 때까지(num의 제곱근 만큼)만 돌면서 약수를 구할 수 있다

100번 for문을 돌아야 했던 걸 10번으로 줄일 수 있다!
숫자가 커질수록 더 효율이 좋아질 것이다 :)

시간복잡도 = O(√n)

2) Math의 sqrt() 사용하기

int num = 100;
int limit = (int) Math.sqrt(num);	//제곱근을 구함

for(int i = 1; i<= limit; i++) {
	if(num % i == 0) {
    	answer ++;
		
        //num을 i로 나눈 몫도 약수 (단, 중복 확인을 피하기 위해 i와 몫이 같지 않을 때만)
        int quotient = num / i;
        if(i != quotient) answer++;
    }
}