โปรแกรม C หาผลรวมตัวประกอบเฉพาะคี่ของตัวเลข

ในส่วนนี้ เราจะดูวิธีหาผลรวมของตัวประกอบเฉพาะคี่ของตัวเลขอย่างมีประสิทธิภาพ มีตัวเลข n = 1092 ตัวประกอบเฉพาะคือ 2, 2, 3, 7, 13 ผลรวมตัวประกอบเฉพาะคี่ = 3+7+13 = 23

กฎการแก้ปัญหา:

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

อัลกอริทึม

printPrimeFactors(n)

begin
    sum := 0
    while n is divisible by 2, do
        n := n / 2
    done
    for i := 3 to √n, increase i by 2, do
        while n is divisible by i, do
            sum := sum + i
            n := n / i
        done
    done
    if n > 2, then
        if n is odd, then
            sum := sum + n
        end if
    end if
end

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

#include <stdio.h>
#include <math.h>

int sumOddFactors(int n) {
    int i, sum = 0;
    while (n % 2 == 0) {
        n = n / 2;
    }
    for (i = 3; i <= sqrt(n); i = 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;
    printf("Enter a number: ");
    scanf("%d", &n);
    printf("Sum of all odd prime factors: %d", sumOddFactors(n));
}

ผลลัพธ์

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