ในส่วนนี้เราจะมาดูกันว่าเราจะหาผลคูณของตัวประกอบเฉพาะของจำนวนอย่างมีประสิทธิภาพได้อย่างไร มีตัวเลขบอกว่า n =1092 เราต้องได้ผลคูณของตัวประกอบเฉพาะของตัวนี้ ตัวประกอบเฉพาะของ 1092 คือ 2, 2, 3, 7, 13 ดังนั้นตัวประกอบเฉพาะเฉพาะคือ {2, 3, 7, 13} ผลคูณคือ 546 ในการแก้ปัญหานี้ เราต้องปฏิบัติตามกฎนี้ −
-
เมื่อตัวเลขหารด้วย 2 ลงตัว ให้คูณ 2 ด้วยผลคูณ แล้วหารจำนวนด้วย 2 ซ้ำๆ จากนั้นระบบจะละเว้น 2 วินาทีถัดไป
-
ตอนนี้ตัวเลขต้องเป็นเลขคี่ ตอนนี้เริ่มจาก 3 ถึงรากที่สองของตัวเลข ถ้าตัวเลขหารด้วยค่าปัจจุบันได้ลงตัว ให้คูณตัวประกอบเข้ากับผลคูณแล้วเปลี่ยนตัวเลขโดยหารด้วยตัวเลขปัจจุบันแล้วทำต่อ ถัดไปจะถูกละเว้นเหมือนด้านบน
-
และสุดท้ายถ้าตัวเลขมากกว่า 2 ก็จะไม่ใช่ 1 ดังนั้นให้คูณจำนวนที่เหลือ
ให้เราดูอัลกอริธึมเพื่อรับแนวคิดที่ดีขึ้น
อัลกอริทึม
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 √𝑛, 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
ตัวอย่าง
#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){ //i will increase by 2, to get only odd numbers
if(n % i == 0){
prod *= i;
n = n/i;
}
while(n % i == 0){ //skip next i's
n = n/i;
}
}
if(n < 2){
prod *= n;
}
return prod;
}
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
