C++で数の奇数の約数（奇因子）の合計を求めるプログラム

正の整数が与えられたとき、その数の奇数の約数（奇因子）をすべて求め、それらの合計を計算するのが本プログラムの目的です。

例

入力: number = 20
出力: 奇数の約数の合計は: 6
入力: number = 18
出力: 奇数の約数の合計は: 13

例えば number = 20 の場合、約数は 1, 2, 4, 5, 10, 20 ですが、このうち奇数は 1 と 5 のみです。したがって、結果 = 1 + 5 = 6 となります。

プログラムで使用するアプローチ

• 奇数の約数の合計を計算する対象の数を入力する
• 偶数の約数を除外するため、まず数を2で割り切れる限り2で割り続け、奇数の部分だけを残す（1は常に奇数の約数として含まれる）
• 3からその数の平方根までループを開始する
• num % i が 0 を返す間、数を i で割り続ける
• ループ内で一時変数を temp = temp * i として更新し続ける
• total を total + temp に設定する（等比級数の合計を求める）
• 最終的な res 変数の値を返し、結果を出力する

アルゴリズム

START
Step 1-> 奇数の約数の合計を計算する関数を宣言
    int sum(int num)
    int res = 1 を宣言
    While(num % 2 == 0) ループ
       num = num / 2 を設定
    終了
    For int i = 3、i <= sqrt(num)、i++ のループ
       int count = 0 と total = 1 を宣言
       int temp = 1 を宣言
       While (num % i == 0) ループ
           count++
           num = num / i を設定
           temp *= i を設定
           total += temp を設定
       終了
       res = res * total を設定
    終了
    IF (num >= 2)
       res *= (1 + num) を設定
    終了
    res を返す
Step 2-> main() 内
    int num = 20 を宣言
    sum(num) を呼び出す
STOP

例

#include <bits/stdc++.h>
using namespace std;
// 奇数の約数の合計を計算する
int sum(int num) {
    int res = 1;
    while (num % 2 == 0)
    num = num / 2;
    for (int i = 3; i <= sqrt(num); i++) {
        int count = 0, total = 1;
        int temp = 1;
        while (num % i == 0) {
            count++;
            num = num / i;
            temp *= i;
            total += temp;
        }
        res = res * total;
    }
    if (num >= 2)
    res *= (1 + num);
    return res;
}
int main() {
    int num = 20;
    cout << "奇数の約数の合計は : ";
    cout << sum(num);
    return 0;
}

出力

奇数の約数の合計は : 6

このプログラムは素因数分解の考え方を利用しています。まず2の因数をすべて取り除き、その後3から平方根までの範囲で奇数の素因数を探します。各素因数 p について (1 + p + p² + ... + p^k) という等比級数の合計を計算し、それらを掛け合わせることで奇数の約数の合計が求まります。計算量は O(√n) であり、大きな数に対しても効率的に処理できるのが特徴です。