การหาจำนวน k-prime ที่มีระยะห่างเฉพาะในช่วงใน JavaScript

จำนวน K-Prime (K-Prime Numbers)

จำนวนธรรมชาติเรียกว่า k-prime ถ้ามีตัวประกอบเฉพาะ (prime factors) ทั้งหมด k ตัว นับซ้ำด้วย (counted with multiplicity)

เช่น 4 มีตัวประกอบเฉพาะคือ 2 เพียงตัวเดียว แต่เป็น 2-prime เพราะ 4 = 2 × 2 นับ 2 ตัว

เช่นเดียวกัน 8 เป็น 3-prime เพราะ 8 = 2 × 2 × 2 นับ 3 ตัว

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข k, ระยะห่าง (distance) และช่วง (range) ฟังก์ชันควรคืนค่าอาร์เรย์ของอาร์เรย์ ที่มีคู่ของ k-prime numbers ภายในช่วง ที่ระยะห่างระหว่างกันเท่ากับ distance ที่กำหนด

ตัวอย่าง

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

const k = 2;
const step = 2;
const range = [0, 50];
const kPrimeSteps = (k = 1, step = 1, [start, end]) => {
  const res = [];
  let i = start;
  const findLen = (n = 1) => {
    let count = 0, i = 2;
    while (i * i <= n) {
      while (n % i === 0) {
        count++;
        n /= i;
      }
      i++;
    }
    if (n > 1) count++;
    return count;
  };
  while (i <= end - step) {
    if ((findLen(i) == k && findLen(i + step) == k))
      res.push([i, i + step]);
    i++;
  }
  return res;
};
console.log(kPrimeSteps(k, step, range));

ผลลัพธ์

[ [ 4, 6 ], [ 33, 35 ] ]

คำอธิบายเพิ่มเติม

ในช่วง 0-50, 2-prime numbers (semiprimes) ที่ห่างกัน 2 คือ (4,6) และ (33,35) โค้ดนับตัวประกอบเฉพาะด้วย trial division สำหรับช่วงใหญ่ควรใช้ Sieve แบบ modified เพื่อนับ omega(n) ทั้งช่วงพร้อมกัน