Sử dụng Sieve of Eratosthenes để tìm số nguyên tố JavaScript

Chúng tôi được yêu cầu viết một hàm JavaScript sử dụng một số, chẳng hạn như n.

Hàm sẽ trả về một mảng tất cả các số nguyên tố từ 1 đến n.

Phương pháp tiếp cận

Bước đầu tiên là tạo một mảng lớn bằng số đã cho, với tất cả các giá trị của nó được khởi tạo là true. Chỉ số mảng sẽ đại diện cho tất cả các số nguyên tố có thể có, với tất cả đều đúng ở đầu.

Sau đó, chúng ta tạo một vòng lặp for lặp từ 2 đến căn bậc hai của một số đã cho. Theo định nghĩa, các tích của bất kỳ số nguyên nào không thể là số nguyên tố, trong khi 0 và 1 bị bỏ qua vì tính chất chia hết cho chúng không ảnh hưởng đến tính nguyên thủy.

Cuối cùng, chúng ta có thể chỉ cần lọc ra tất cả các giá trị sai để thu được tất cả các số nguyên tố.

Ví dụ

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[
   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
]