จำนวนเฉพาะ (Prime Number) คือจำนวนธรรมชาติที่มากกว่า 1 ซึ่งไม่สามารถสร้างขึ้นได้จากการคูณจำนวนธรรมชาติอีกสองจำนวนที่เล็กกว่า จำนวนธรรมชาติส่วนที่เหลือที่มากกว่า 1 เรียกว่าจำนวนประกอบ (Composite Number) การทดสอบจำนวนเฉพาะ (Primality Test) เป็นอัลกอริทึมสำหรับตรวจสอบว่าตัวเลขที่ป้อนเข้ามาเป็นจำนวนเฉพาะหรือไม่
ตัวอย่างโค้ด
ฟังก์ชันต่อไปนี้ตรวจสอบว่าเลขที่รับเข้ามาเป็นจำนวนเฉพาะหรือไม่:
const findPrime = (num = 2) => {
if (num % 1 !== 0) {
return false;
}
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 === 0) {
return false;
}
const dividerLimit = Math.sqrt(num);
for (let divider = 3; divider <= dividerLimit; divider += 2) {
if (num % divider === 0) {
return false;
}
}
return true;
};
console.log(findPrime(2)); // true
console.log(findPrime(97)); // true
console.log(findPrime(131)); // true
console.log(findPrime(343)); // false
ผลลัพธ์
true true true false
คำอธิบายการทำงาน
- ตรวจสอบว่าเป็นจำนวนเต็มหรือไม่ (num % 1 !== 0)
- เลข 1 และเลขติดลบไม่ใช่จำนวนเฉพาะ
- เลข 2 และ 3 เป็นจำนวนเฉพาะ
- เลขคู่ที่มากกว่า 2 ไม่ใช่จำนวนเฉพาะ
- ตรวจสอบตัวหารเฉพาะเลขคู่จาก 3 ถึงรากที่สองของตัวเลข
- ซับซ้อนทางเวลา: O(√n)
