[C 언어] 백준 #17427 - 약수의 합

문제

---

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

 

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

입력	출력
1	1
2	4
10	87

 

 

풀이

---

처음에 푼 방식

1부터 N까지 하나씩 약수를 확인한 후 약수의 합을 구했다. i가 1부터 4까지, j가 1부터 i까지 도는 이중 for문을 사용하였다. 

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	int sum = 0;

	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			if (i % j == 0)
				sum += j;
		}
	}

	printf("%d\n", sum);

	return 0;
}

 

그러나 이 방식은 시간 초과로 실패하였다. 

 

두 번째 푼 방식

몫을 활용한다.

 

예를 들어, N을 5로 가정

5 이하의 수 중 1을 약수로 가지는 수의 개수: 5

5 이하의 수 중 2을 약수로 가지는 수의 개수: 2

5 이하의 수 중 3을 약수로 가지는 수의 개수: 1

5 이하의 수 중 4을 약수로 가지는 수의 개수: 1

5 이하의 수 중 5을 약수로 가지는 수의 개수: 1

 

여기서 개수는 5를 어떤 수로 나눴을 때, 몫이 된다. >> N / i

N = 5, g(N) = 21

 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	long long sum = 0;

	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		sum += (N / i) * i;
	}

	printf("%d\n", sum);

	return 0;
}