หาผลรวมของตัวประกอบคี่ของจำนวนด้วย C++

ในส่วนนี้ เราจะดูวิธีที่เราสามารถหาผลรวมของตัวประกอบเฉพาะคี่ (Odd Prime Factors) ของจำนวนได้อย่างมีประสิทธิภาพ มีจำนวนเช่น n = 1092 เราต้องหาตัวประกอบทั้งหมด ตัวประกอบเฉพาะของ 1092 คือ 2, 2, 3, 7, 13 ผลรวมของตัวประกอบคี่ทั้งหมดคือ 3+7+13 = 23 เพื่อแก้ปัญหานี้ เราต้องปฏิบัติตามกฎนี้ -

• เมื่อจำนวนหาร 2 ลงตัว ให้ละเว้นตัวประกอบนั้น และหารจำนวนด้วย 2 ซ้ำๆ
• ตอนนี้จำนวนต้องเป็นคี่ เริ่มจาก 3 ถึงรากที่สองของจำนวน ถ้าจำนวนหารด้วยค่าปัจจุบันลงตัว ให้บวกตัวประกอบกับผลรวม และเปลี่ยนจำนวนโดยการหารด้วยค่าปัจจุบัน แล้วทำต่อ
• สุดท้าย จำนวนที่เหลือก็จะถูกบวกด้วยถ้าจำนวนที่เหลือเป็นคี่

อัลกอริทึม

printPrimeFactors(n):
begin
    sum := 0
    while n หาร 2 ลงตัว do
        n := n / 2
    done
    for i := 3 ถึง sqrt(n) เพิ่ม i ทีละ 2 do
        while n หาร i ลงตัว do
            sum := sum + i
            n := n / i
        done
    done
    if n > 2 then
        if n เป็นคี่ then
            sum := sum + n
        end if
    end if
end

ตัวอย่างโค้ด

#include <iostream>
#include <cmath>
using namespace std;

int sumOddFactors(int n) {
    int i, sum = 0;
    while (n % 2 == 0) {
        n = n / 2; // ลด n โดยการหารด้วย 2
    }
    // เนื่องจากจำนวนไม่หาร 2 ลงตัวแล้ว ตัวประกอบทั้งหมดเป็นคี่
    for (i = 3; i <= sqrt(n); i = i + 2) { // i เพิ่มทีละ 2 เพื่อได้เฉพาะเลขคี่
        while (n % i == 0) {
            sum += i;
            n = n / i;
        }
    }
    if (n > 2) {
        if (n % 2 == 1)
            sum += n;
    }
    return sum;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Sum of all odd prime factors: " << sumOddFactors(n);
}

ผลลัพธ์

Enter a number: 1092
Sum of all odd prime factors: 23