ในส่วนนี้ เราจะมาดูกันว่าเราจะหาผลรวมของตัวประกอบเฉพาะที่เป็นจำนวนคู่ทั้งหมดของจำนวนอย่างมีประสิทธิภาพได้อย่างไร มีตัวเลขบอกว่า n =480 เราต้องหาตัวประกอบทั้งหมดของมัน ตัวประกอบเฉพาะของ 480 คือ 2, 2, 2, 2, 2, 3, 5 ผลรวมของตัวประกอบคู่ทั้งหมดคือ 2+2+2+2+2 =10 ในการแก้ปัญหานี้ เราต้องปฏิบัติตามกฎนี้ −
- เมื่อตัวเลขหารด้วย 2 ลงตัว ให้บวกเข้ากับผลรวมแล้วหารตัวเลขด้วย 2 ซ้ำๆ
- ตอนนี้ตัวเลขต้องเป็นเลขคี่ ดังนั้นเราจะไม่พบปัจจัยที่เท่ากัน จากนั้นให้เพิกเฉยต่อปัจจัยเหล่านั้น
มาดูอัลกอรึทึมกันดีกว่าครับ
อัลกอริทึม
printPrimeFactors(n): begin sum := 0 while n is divisible by 2, do sum := sum + 2 n := n / 2 done end
ตัวอย่าง
#include<iostream>
using namespace std;
int sumEvenFactors(int n){
int i, sum = 0;
while(n % 2 == 0){
sum += 2;
n = n/2; //reduce n by dividing this by 2
}
return sum;
}
main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout << "Sum of all even prime factors: "<< sumEvenFactors(n);
} ผลลัพธ์
Enter a number: 480 Sum of all even prime factors: 10
