약수

어떤 수 N을 나누었을 때 나머지가 0이 되는 수

예시

N: 10
1부터 10까지의 숫자로 10을 나눈다.
이때 나머지가 0이면 해당 수는 N의 약수

10 / 1 일때, 몫: 10, 나머지 0 / 따라서 1은 10의 약수
10 / 2 일때, 몫:  5, 나머지 0 / 따라서 2는 10의 약수
.
.
.
10 / 10 일때, 몫: 1, 나머지 0 / 따라서 10은 10의 약수

코드

/*
	의사 코드
    N = 10
    1부터 N까지 반복
    	1부터 N까지 수 중에 나머지가 0이면
        	약수, 따라서 리스트에 추가
    	
*/
int N = 10;
ArrayList<Integer> list = new ArrayList<>();

// 1부터 N까지 반복
for	(int i = 1; i <= N; i++) {
	if (N % i == 0) {
    	list.add(i);
	}
}

// 약수가 저장된 리스트 출력
System.out.println(list);

개선

위에서 10을 1로 나눌 때 몫이 10이었다. 10으로 10을 나누었을 때 몫이 1이 었다.

결국 둘다 약수이다. 1로 나누었을 때 0으로 떨어진다면 해당 몫도 약수가 되는 것이다.

제곱근을 기준으로 절반만 나눗셈을 수행하면 훨씬 빠른 계산 결과를 얻을 수 있다.

• 1 x 16
• 2 x 8
• 4 x 4 : 16의 제곱근
• 8 x 2
• 16 x 1

16의 제곱근을 기준으로 좌우만 바뀐 똑같은 연산이 발생됨, 따라서 1부터 4까지만 16으로 나누고 0으로 떨어지면 나눈 값과 몫을 동시에 약수로 저장하면 연산을 절반이나 줄일 수 있다.

N: 10
1부터 10의 제곱근을 넘지 않는 정수까지의 숫자로 N을 나눈다.
나머지가 0이라면, 나눈 수, 몫이 약수이다.

10 / 1, 몫: 10, 나머지: 0
10 / 10, 몫: 1, 나머지: 0
1로 나누었을 때 몫: 10도 약수임을 알 수 있는데, 굳이 10 / 10를 수행한다면 효율이 떨어진다.
그래서 제곱근을 기준으로 연산의 횟수를 절반을 줄일 수 있다.

코드

/*
	의사코드
    N = 10
    1부터 N의 제곱근 까지 반복(i에 대입)
    	i로 N을 나누었을 때 나머지가 0이면
        	i의 제곱이 n과 같다면
            	리스트에 i추가
			i의 제곱이 아니라면
            	리스트에 i추가
                리스트에 i로 N을 나눴을 때 몫 추가.
*/
int n = 10;
double sqrt = Math.sqrt(n);
ArrayList<Integer> list = new ArrayList<>();

for (int i = 1; i <= sqrt; i++) {
	if (n % i == 0) {
    	if (Math.pow(i, 2) == n) {
        	list.add(i);
		} else {
        	list.add(i);
            list.add(n / i);
		}
	}
}

Collections.sort(list);	// 보기 좋게 오름차순 정렬
System.out.println(list);

N % i == 0일때 i를 제곱하여 N과 비교한 이유는 제곱근이 정수로 떨어지는 경우가 있기 때문에 해당 사항에서는 몫과 나눈 값을 동시에 추가하면, 중복이 발생한다.

예들들어 16의 제곱근 4이다. 반복문을 계속 실행하다보면 i = 4가 해당되는 시점이 나온다. 이때 16 / 4 = 4, 나머지 = 0인데, i와 나머지 4를 약수 리스트에 둘다 추가한다면 4가 중복된다. 이를 방지하기 위해 i의 제곱이 N과 같은지 비교해야 하는 것이다.