ความรู้พื้นฐาน
ปัจจัยเฉพาะ (Prime Factor) คือจำนวนเฉพาะที่เป็นตัวประกอบของตัวเลขที่กำหนด
ตัวประกอบ (Factor) คือตัวเลขที่คูณกันเพื่อให้ได้ตัวเลขที่กำหนด
การแยกตัวประกอบเฉพาะ (Prime Factorisation) คือกระบวนการหารตัวเลขด้วยปัจจัยเฉพาะซ้ำๆ จนหาปัจจัยเฉพาะทั้งหมด
ตัวอย่าง
N = 120 ปัจจัยเฉพาะ = 2, 5, 3 การแยกตัวประกอบ: 2 × 2 × 2 × 3 × 5
ข้อสังเกตสำคัญ
- ชุดของปัจจัยเฉพาะของตัวเลขแต่ละตัวมีค่าเฉพาะตัว (unique)
- การแยกตัวประกอบสำคัญในการคำนวณทางคณิตศาสตร์ เช่น การหารลงตัว หาตัวหารร่วมน้อย
- เป็นแนวคิดสำคัญในทฤษฎีการเข้ารหัส (Cryptography)
โปรแกรมหาปัจจัยเฉพาะ
#include <iostream>
#include <math.h>
using namespace std;
void printPrimeFactors(int n) {
while (n % 2 == 0) {
cout << "2\t";
n = n / 2;
}
for (int i = 3; i <= sqrt(n); i = i + 2) {
while (n % i == 0) {
cout << i << "\t";
n = n / i;
}
}
if (n > 2)
cout << n << "\t";
}
int main() {
int n = 2632;
cout << "Prime factors of " << n << " are :\t";
printPrimeFactors(n);
return 0;
}
ผลลัพธ์
Prime factors of 2632 are : 2 2 2 7 47
