การใช้ Sieve of Eratosthenes เพื่อค้นหาจำนวนเฉพาะ JavaScript

เราต้องเขียนฟังก์ชัน JavaScript ที่รับค่าตัวเลข เช่น n.

ฟังก์ชันควรส่งคืนอาร์เรย์ของจำนวนเฉพาะทั้งหมดระหว่าง 1 ถึง n

แนวทาง

ขั้นตอนแรกคือการสร้างอาร์เรย์ที่มีขนาดใหญ่เท่ากับจำนวนที่กำหนด โดยค่าทั้งหมดเริ่มต้นเป็นจริง ดัชนีอาร์เรย์จะแสดงจำนวนเฉพาะที่เป็นไปได้ทั้งหมด โดยทั้งหมดเป็นจริงที่จุดเริ่มต้น

จากนั้น เราสร้าง for loop ที่วนซ้ำจาก 2 ถึงรากที่สองของจำนวนที่กำหนด ตามคำจำกัดความ ผลคูณของจำนวนเต็มไม่สามารถเป็นจำนวนเฉพาะได้ ในขณะที่ 0 และ 1 จะถูกละเว้นเนื่องจากการหารด้วยจำนวนเต็มนั้นไม่ส่งผลต่อความเป็นอันดับหนึ่ง

สุดท้ายนี้ เราสามารถกรองค่าเท็จทั้งหมดเพื่อให้ได้จำนวนเฉพาะทั้งหมด

ตัวอย่าง

const num =100;const findPrimes =(num =10) => { const numArr =อาร์เรย์ใหม่ (num + 1); numArr.fill(จริง); numArr[0] =numArr[1] =เท็จ; for (ให้ i =2; i <=Math.sqrt(num); i++) { สำหรับ (ให้ j =2; i * j <=num; j++){ numArr[i * j] =false; } } ส่งคืน numArr.reduce((acc, val, ind) => { if(val){ return acc.concat(ind); }else{ return acc; }; },[]);};console.log( findPrimes(num));

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −