자바로 약수의 개수 구하기 알고리즘

약수의 개수 구하기

첫번째 방법

// 구해야할 약수의 범위 1~10
int number = 10;

for(int i = 1; i <= number; i++){
	int count = 0;
	for(int j = 1; j * j <= i; j++){
		if(j * j == i) count ++;
		else if (i % j == 0) count += 2;
	}
}

int i = 약수를 구할 숫자 (1 ~ 10)

int j = i의 약수인지 판별할 숫자

약수의 개수를 구할 때는 구할 수의 제곱근까지만 판별하면 됨
x * x = number  일 때는 약수의 개수를 1개 카운트하고 
x * y = number  일 때는 x가 약수라는 것만 알면 y도 약수라는 것을 알 수 있기때문에 2개로 카운트해주면됨

 

두번째 방법

// 구해야 할 약수의 범위 1~10
int number = 10;

int[] count = new int[number + 1];
        
for(int i = 1; i <= number ; i++){
	for(int j = 1; j <= number / i; j++){
		count[i*j] ++;
	}
}

인덱스의 약수 개수를 저장할 count 배열을 선언.  0은 약수가 아니기 때문에 number보다 +1해서 선언

반복문을 돌리면서 i * j 인덱스에 1씩 추가   ->       i * j = k 라면 k의 i와 j는 k의 약수이기 때문이다

j의 조건을 j <= number / i로 지정하는 이유는 i * j 가 number보다 클 경우는 무조건 약수가 아니고 구할 필요가 없다.

 

 

쉬운 건데 왜 이렇게 헷갈리는 지 모르겠담