진약수 구하기

일반적인 방법, n까지 for문 돌면서 나머지가 0인 i의 합을 구하면 된다.
이 때 진약수는 대칭적으로 나타나기 때문에 n/2이후는 중복 계산이 된다. n/2까지만 for문을 돌린다.

#include<iostream>

using namespace std;

int main()
{
	int n, m;
	int sum = 0;
	cin >> n;

	for (int i = 1; i <= n/2; i++)
	{
		if (n % i == 0)
		{
			sum += i;
		}
	}

	cout << sum << endl;
	return 0;
}

[최적화 방법 1]  i * i <=n을 이용한 최적화
 - for문에서 1부터 n까지 모든 수를 탐색하면서 i가 n의 약수인지 확인하는 것보다 i가 n의 제곱근보다 작거나 같은 경우만을 탐색하는 것이 더 효율적. 중복되는 약수를 한 번씩만 계산하게 된다.

int divisorSum(int n) {
	int sum = 1;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			sum += i;
			if (i * i != n) {
				sum += (n / i);
			}
		}
	}
	return sum;
}

-> 생각해보면 간단, n이 12일 때
1 2 3 4 5 6 7 8 9 10 11 12를 쭉 탐색하는 것이 아니라,
1) 2부터 시작해서,
2) n % i == 0 -> n이 i로 나누어지는 값은 약수.
  i가 2일 때, 2는 12를 나눌 수 있는 약수다.
  n을 i인 2로 나누면, n / i. 즉 12 /2 = 6이 나오는데 6도 n을 나눌 수 있는 약수이다.

 그렇기 때문에 for 문을 전체를 돌리는 게 아니라 처음 나오는 약수인 2와 12를 2로 나누어서 나온 6을 한번에 확인하여 반복 횟수를 줄인다.
 반복문은 i*i<=n만큼만 반복하여 횟수를 줄이는데  i*i가 n을 넘었다는 건 이미 확인할 범위를 넘었기 때문에 확인할 필요없다.

[최적화 2] 에라토스테네스의 체를 이용

*에라토스테네스의 체 : 소수를 찾는 알고리즘, 주어진 범위 안에소 소수를 찾을 때 사용
알고리즘의 동작 방식은 다음과 같다.

1. 주어진 범위의 자연수를 모두 나열한다.
2. 2부터 시작해서 2의 배수를 모두 제거한다.
3. 다음으로 남아있는 수 중에서 가장 작은 수를 찾아서 그 수의 배수를 모두 제거한다.
4. 3번을 반복. 만약 범위 안의 모든 수를 다 검사했다면 알고리즘을 종료한다.

int n = 100; // 찾을 범위
vector<bool> is_prime(n+1, true); // 소수 여부를 나타내는 배열

is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님

for (int i = 2; i * i <= n; i++) { // i는 2부터 sqrt(n)까지 반복
    if (is_prime[i]) { // i가 소수일 때
        for (int j = i * i; j <= n; j += i) { // i의 배수를 제거
            is_prime[j] = false;
        }
    }
}

위와 같이 에리토스테네스의 체를 활용하여 소수가 아닌 값들을 제거 하는 방법을 응용하여 진약수를 구한다.
결국 1~n까지 돌면서, '소수가 아닌 값 = i의 배수인 값'들은 제거하는 방식. i의 배수란 건 소수가 아님.

vector<int> divisorSum(int n) {
    vector<int> sum(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            sum[j] += i;
        }
    }
    return sum;
}

배열 sum에는 1~i까지의 약수의 합이 sum[i]에 저장된다. 이러한 방법은 전처리 과정이 필요하지만 여러번 쿼리를 수행하는 경우 유용하다.

방법은 이렇다.
1은 빼고, sum[i] = 1로 초기화.
2~n만큼 돌면서 '에리토스테네스의 체' 알고리즘을 응용.
 ->  sum[i]에는 2~i번째 까지의 약수의 합을 더한다.
 2부터 순차적으로 돌면서 2의 배수인 sum[i*2]값에 2를 더해준다. 2는 2,4,6,8,10의 약수이니까.
마찬가지로 3은 sum[i*3]에 더해주며, 4는 sum[i*4]에 더해준다.

코드의 아랫 부분. 결국 간단히 얘기하면 sum 배열에 각 약수값을 하나씩 더해나간다고 생각하면 된다.

for (int i = 2; i <= n; i++) { // 2부터 순차적으로 돌면서,
        for (int j = i; j <= n; j += i) { //i의 배수만큼 돈다.
            sum[j] += i; //sum[j]에는 약수 i를 더한다.
        }
    }

즉, 
sum[1] = 1
sum[2] = 1 + 2
sum[3] = 1 + 2 + 3
sum[4] = 1 + 2 + 4
sum[5] = 1 + 2 + 5
sum[6] = 1 + 2 + 3 + 6 
sum[7] = 1 + 7
sum[8] = 1 + 2 + 4 + 8