ในส่วนนี้ เราจะมาดูกันว่าเราจะหาผลรวมของตัวประกอบจำนวนเฉพาะคี่ทั้งหมดของตัวเลขอย่างมีประสิทธิภาพได้อย่างไร มีตัวเลขว่า n =1092 เราต้องหาตัวประกอบทั้งหมดของมัน ตัวประกอบเฉพาะของ 1092 คือ 2, 2, 3, 7, 13 ผลรวมของตัวประกอบคี่ทั้งหมดคือ 3+7+13 =23 ในการแก้ปัญหานี้ เราต้องปฏิบัติตามกฎนี้ –
- เมื่อตัวเลขหารด้วย 2 ลงตัว ให้ข้ามตัวประกอบนั้นไป แล้วหารจำนวนด้วย 2 ซ้ำๆ
- ตอนนี้ตัวเลขต้องเป็นเลขคี่ ตอนนี้เริ่มจาก 3 ถึงรากที่สองของตัวเลข หากตัวเลขหารด้วยค่าปัจจุบันได้ลงตัว ให้บวกตัวประกอบกับผลรวม แล้วเปลี่ยนตัวเลขโดยหารด้วยตัวเลขปัจจุบันแล้วดำเนินการต่อ
- สุดท้ายตัวเลขที่เหลือจะถูกเพิ่มเข้าไปด้วยหากตัวเลขที่เหลือเป็นเลขคี่
มาดูอัลกอรึทึมกันดีกว่าครับ
อัลกอริทึม
printPrimeFactors(n): begin sum := 0 while n is divisible by 2, do n := n / 2 done for i := 3 to , increase i by 2, do while n is divisible by i, do sum := sum + i n := n / i done done if n > 2, then if n is odd, then sum := sum + n end if end if end
ตัวอย่าง
#include<iostream>
#include<cmath>
using namespace std;
int sumOddFactors(int n){
int i, sum = 0;
while(n % 2 == 0){
n = n/2; //reduce n by dividing this by 2
}
//as the number is not divisible by 2 anymore, all factors are odd
for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
while(n % i == 0){
sum += i;
n = n/i;
}
}
if(n > 2){
if(n%2 == 1)
sum += n;
}
return sum;
}
main() {
int n;
cout << "Enter a number: ";
cin >> n;
cout <<"Sum of all odd prime factors: "<< sumOddFactors(n);
} ผลลัพธ์
Enter a number: 1092 Sum of all odd prime factors: 23
