โปรแกรม C พิมพ์ตัวประกอบเฉพาะทั้งหมดของตัวเลขอย่างมีประสิทธิภาพ

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

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

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

อัลกอริทึม

printPrimeFactors(n)

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

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

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

void primeFactors(int n) {
    int i;
    while (n % 2 == 0) {
        printf("%d, ", 2);
        n = n / 2;
    }
    for (i = 3; i <= sqrt(n); i = i + 2) {
        while (n % i == 0) {
            printf("%d, ", i);
            n = n / i;
        }
    }
    if (n > 2) {
        printf("%d, ", n);
    }
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    primeFactors(n);
}

ผลลัพธ์

Enter a number: 24024
2, 2, 2, 3, 7, 11, 13,