โปรแกรม C หาตัวประกอบเฉพาะที่ใหญ่ที่สุดของตัวเลข

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

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

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

อัลกอริทึม

getMaxPrimeFactors(n)

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

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

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

int getMaxPrimeFactor(int n) {
    int i, max = -1;
    while (n % 2 == 0) {
        max = 2;
        n = n / 2;
    }
    for (i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            max = i;
            n = n / i;
        }
    }
    if (n > 2) {
        max = n;
    }
    return max;
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    printf("Max prime factor: %d", getMaxPrimeFactor(n));
}

ผลลัพธ์

Enter a number: 24024
Max prime factor: 13