[Java] 약수의 개수 구하기

▤ 목차

1. 약수의 개수 구하기

1. 방법1

int N = 12345; // 숫자
int cnt = 0; // 약수의 개수
        for(int i=1; i<=N; i++){
           if(N%i == 0){
              cnt++; 
           } 
        }

이 방법은 number가 커질수록 비효율적이다.

 

2. 방법2 (효율적인 방법)

int N = 12345; //숫자
int cnt = 0; //약수의 개수
for (int i = 1; i*i <= N; i++) {
	if (i*i == N) cnt++;
	else if (N % i == 0) cnt += 2;
}

N의 약수 중 하나가 m이라고 했을 때, 다른 약수는 number/m이 되므로 하나의 약수를 알면 다른 하나를 알수있다.

for문을 √N까지 구하면 약수 절반의 개수를 구할 수 있다는 걸 알 수 있다.

즉 1~√N까지 수 중 N의 약수를 구해 × 2를 해주면 되고, 약수가 √N인 경우에 제곱근이므로 1개로 카운트해주면 된다.

3. 방법3 (제일 효율적인 방법)

int N = 12345; //숫자
int cnt = 0; //약수의 개수
int sqrt = (int) Math.sqrt(N); // 제곱근을 구하기 

for(int i = 1; i <= sqrt; i++){
	if (i*i == N) cnt++;
	else if (N % i == 0) cnt += 2;
}

제곱근을 구해주는 Math.sqrt() 메서드를 활용하면 코드를 더 축약할 수 있다.

 

https://chwan.tistory.com/entry/Java-%EC%95%BD%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

[Java] 약수의 개수 구하기

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.