[백준] 2247번 : 실질적 약수 (C++)

2247번 : 실질적 약수

---

문제)

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다.

실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다.

 

SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1) + SOD(2) + … + SOD(n)이라고 하자.

CSOD(n)을 구하는 프로그램을 작성하시오.

 

 

 

 

입력 :

첫째 줄에 정수 n이 주어진다.

 

 

 

출력 :

첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.

 

 

 

 

 

풀이)

 

// 2247. 실질적 약수
#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    
    int answer = 0;
    
    // sod(n)을 구하는 것이 아닌, 
    // 약수의 개수를 세어준다.
    for (int i = 2; i < n + 1; i++)
    {
        int cnt = n / i;
        answer += (cnt - 1) * i;
        answer %= 1000000;
    }
 
    cout << answer;
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/2247 

2247번: 실질적 약수