Sử dụng Sàng Eratosthenes tìm số nguyên tố trong JavaScript

Cần viết hàm JavaScript nhận số n. Hàm trả về mảng tất cả số nguyên tố từ 1 đến n.

Cách tiếp cận

Bước đầu tạo mảng kích thước bằng số cho trước, tất cả giá trị khởi tạo true. Chỉ số mảng đại diện cho các số nguyên tố tiềm năng, tất cả true ban đầu.

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

Cuối cùng, lọc tất cả giá trị false để được tất 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));

Kết quả

Kết quả trong console 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 
]