ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะใน JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข n ฟังก์ชันควรคืนค่าอาร์เรย์ของจำนวนเฉพาะทั้งหมดระหว่าง 1 และ n

วิธีการ

ขั้นตอนแรกคือสร้างอาร์เรย์ใหญ่เท่าตัวเลขที่ให้มา โดยมีค่าเริ่มต้นทั้งหมดเป็น true ดัชนีของอาร์เรย์จะแทนจำนวนเฉพาะที่เป็นไปได้ทั้งหมด โดยทั้งหมดเป็น true ตั้งแต่แรก จากนั้นเราสร้างลูป for ที่วนจาก 2 ถึงรากที่สองของตัวเลขที่ให้มา โดยนิยาม ผลคูณของจำนวนเต็มใดๆ ไม่สามารถเป็นจำนวนเฉพาะได้ ในขณะที่ 0 และ 1 ถูกละเว้นเพราะการหารลงตัวด้วยพวกมันไม่ส่งผลต่อความเป็นจำนวนเฉพาะ สุดท้าย เราสามารถกรองค่า false ทั้งหมดออกเพื่อให้ได้จำนวนเฉพาะทั้งหมด

ตัวอย่าง

const num = 100;
const findPrimes = (num = 10) => {
  const numArr = new Array(num + 1);
  numArr.fill(true);
  numArr[0] = numArr[1] = false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    for (let j = 2; i * j <= num; j++){
      numArr[i * j] = false;
    }
  }
  return numArr.reduce((acc, val, ind) => {
    if(val){
      return acc.concat(ind);
    }else{
      return acc;
    };
  },[]);
};
console.log(findPrimes(num));

ผลลัพธ์

ผลลัพธ์ในคอนโซลจะเป็นดังนี้:

[
  2, 3, 5, 7, 11, 13, 17, 19,
  23, 29, 31, 37, 41, 43, 47, 53,
  59, 61, 67, 71, 73, 79, 83, 89,
  97
]