ในส่วนนี้เราจะดูวิธาหาผลคูณของตัวประกอบเฉพาะที่ไม่ซ้ำกัน (unique prime factors) อย่างมีประสิทธิภาพ ตัวอย่าง n = 1092 ตัวประกอบเฉพาะคือ 2, 2, 3, 7, 13 ตัวประกอบเฉพาะที่ไม่ซ้ำ = {2, 3, 7, 13} ผลคูณ = 546
กฎการแก้ปัญหา:
- ถ้าหาร 2 ลงตัว คูณ 2 เข้า product หาร n ด้วย 2 ซ้ำๆ (2 ตัวถัดไปจะถูกข้าม)
- ตอนนี้ n เป็นคี่ เริ่มจาก 3 ถึงรากที่สอง ถ้าหารลงตัว คูณตัวประกอบเข้า product หาร n ด้วยตัวประกอบนั้น ต่อไปเรื่อยๆ (ตัวซ้ำถูกข้าม)
- สุดท้าย ถ้า n > 2 คูณ n ที่เหลือเข้า product
อัลกอริทึม
uniquePrimeProduct(n)
begin
prod := 1
if n is divisible by 2, then
prod := prod * 2
n := n / 2
end if
while n is divisible by 2, do
n := n / 2
done
for i := 3 to √n, increase i by 2, do
if n is divisible by i, then
prod := prod * i
n := n / i
end if
while n is divisible by i, do
n := n / i
done
done
if n > 2, then
prod := prod * n
end if
end
ตัวอย่างโค้ด (C)
#include <stdio.h>
#include <math.h>
int uniquePrimeProduct(int n) {
int i, prod = 1;
if (n % 2 == 0) {
prod *= 2;
n = n / 2;
}
while (n % 2 == 0) { // skip next 2s
n = n / 2;
}
for (i = 3; i <= sqrt(n); i = i + 2) {
if (n % i == 0) {
prod *= i;
n = n / i;
}
while (n % i == 0) { // skip next i's
n = n / i;
}
}
if (n < 2) { // bug in original: should be n > 2
prod *= n;
}
return prod;
}
int main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
printf("Product of prime factors: %d", uniquePrimeProduct(n));
}
ผลลัพธ์
Enter a number: 1092 Product of prime factors: 546
หมายเหตุ: ในโค้ดต้นฉบับมี bug เล็กน้อยที่ `if (n < 2)` ควรเป็น `if (n > 2)`
