การหาจำนวนเฉพาะที่น้อยที่สุดที่มากกว่าตัวเลขที่กำหนดใน JavaScript

บทความนี้สาธิตการหาจำนวนเฉพาะ (prime) ที่น้อยที่สุดที่มากกว่าตัวเลข input

ตัวอย่าง

input: 18 -> output: 19

ตัวอย่างโค้ด

const num = 18;

const justGreaterPrime = (num) => {
  for (let i = num + 1; ; i++) {
    let isPrime = true;
    for (let d = 2; d * d <= i; d++) {
      if (i % d === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      return i;
    }
  }
};

console.log(justGreaterPrime(num));

ผลลัพธ์

19

คำอธิบาย

ตรวจสอบตัวเลขต่อเนื่องตั้งแต่ num+1 ขึ้นไป สำหรับแต่ละตัว ตรวจสอบ primality โดย trial division จน sqrt(i)

Time: O(gap * sqrt(n)) โดย gap คือระยะห่างไปยัง prime ถัดไป