Bài 01: Kiểm tra số nguyên tố bằng Javascript

Xin giới thiệu và ra mắt serie học javascript qua các bài tập thực hành, đây là một serie cung cấp các ví dụ để học Javascript một cách nhanh và dễ tiếp thu nhất, hy vọng qua serie này các bạn sẽ thích thú với ngôn ngữ Client này và thích luôn cả freetuts.net cheeky.

Bài đầu tiên này chúng ta sẽ vận dụng kiến thức về khai báo biếnvòng lặp for, hàm và câu điều kiện if else để giải bài tập kiểm tra một số có phải là số nguyên tố hay không bằng Javascript, bài tập này chúng ta sẽ thực hiện nhiều cách khác nhau và mình sẽ giải thích ý tưởng cho từng cách.

Trước khi vào phần bài giải thì bạn xem qua khái niệm số nguyên tố là gì đã nhé.

1. Thuật toán kiểm tra số nguyên tố trong Javascript (1)

Trong thuật toán này ta bám sát vào khái niệm của số nguyên tố đó là "số nguyên tố là số lớn hơn 1 và chia hết cho 1 và chính nó". Như vậy ta sẽ dùng một vòng lặp for lặp từ 2 -> (n-1) và trong quá trình lặp nếu tốn tại số mà n chia hết thì tức là không phải số nguyên tố.

XEM DEMO

function kiem_tra_snt(n)
{
    // Biến cờ hiệu
    var flag = true;

    // Nếu n bé hơn 2 tức là không phải số nguyên tố
    if (n < 2){
        flag = false;
    }
    else{
        // lặp từ 2 tới n-1
        for (var i = 2; i < n-1; i++)
        {
            if (n % i == 0){
                flag = false;
                break;
            }
        }
    }

    // Kiểm tra biến flag
    if (flag == true){
        document.write(n + " là số nguyên tố <br/>");
    }
    else{
        document.write(n + " không phải là số nguyên tố <br/>");
    }
}

2. Thuật toán kiểm tra số nguyên tố trong Javascript (2)

Kế thừa từ định nghĩa và tính chất "số 2 là số nguyên tố chẵn duy nhất" ta sẽ thực hiện các bước sau để kiểm tra:

  • Nếu n < 1 => là không phải số nguyên tố
  • Nếu n = 2 => là số nguyên tố
  • Nếu n % 2 == 0 => không phải là số nguyên tố
  • Lặp từ 3 -> (n-1) với bước nhảy là 2 (chỉ lặp các số lẻ) và trong quá trình lặp nếu tồn tại số mà n chia hết thì n không phải là số nguyên tố

Như vậy với cách này ta giảm tải được 1/2 số lần lặp.

XEM DEMO

function kiem_tra_snt(n)
{
    // Biến cờ hiệu
    var flag = true;

    // Nếu n bé hơn 2 tức là không phải số nguyên tố
    if (n < 2){
        flag = false;
    }
    else if (n == 2){
        flag = true;
    }
    else if (n % 2 == 0){
      flag = false;
    }
    else{
        // lặp từ 3 tới n-1 với bước nhảy là 2 (i+=2)
        for (var i = 3; i < n-1; i+=2)
        {
            if (n % i == 0){
                flag = false;
                break;
            }
        }
    }

    // Kiểm tra biến flag
    if (flag == true){
        document.write(n + " là số nguyên tố <br/>");
    }
    else{
        document.write(n + " không phải là số nguyên tố <br/>");
    }
}

3. Thuật toán kiểm tra số nguyên tố trong Javascript (3)

Kế thừa từ thuật toán thứ hai ta vận dụng thêm tính chất "n là số nguyên tố thì trong khoảng từ 2 đến căn bậc hai cua n sẽ không tồn tại số mà n chia hết" ta sẽ giảm đi được hơn 1/2 lần lặp nữa, tuy nhiên ta sẽ phải mất chi phí tính căn bậc hai.

Như vậy ta chỉ cần sửa lại ở thuật toán thứ hai thay điều kiện dừng vòng lặp là từ 3 -> Math.sqrt(n).

Lưu ý: Để tính căn bậc hai của một số trong Javasccript ta sử dụng hàm Math.sqrt(n).

XEM DEMO

function kiem_tra_snt(n)
{
    // Biến cờ hiệu
    var flag = true;

    // Nếu n bé hơn 2 tức là không phải số nguyên tố
    if (n < 2){
        flag = false;
    }
    else if (n == 2){
        flag = true;
    }
    else if (n % 2 == 0){
      flag = false;
    }
    else{
        // lặp từ 3 tới n-1 với bước nhảy là 2 (i+=2)
        for (var i = 3; i < Math.sqrt(n); i+=2)
        {
            if (n % i == 0){
                flag = false;
                break;
            }
        }
    }

    // Kiểm tra biến flag
    if (flag == true){
        document.write(n + " là số nguyên tố <br/>");
    }
    else{
        document.write(n + " không phải là số nguyên tố <br/>");
    }
}

Lời kết

Như vậy mỗi cách kiểm tra số nguyên tố có những ưu và nhược điểm khác nhau và theo mình thì nên chọn giải pháp thứ 3 để giải vì đối với số lớn nếu sử dụng vòng lặp quá nhiều thì sẽ mất khá nhiều thời gian để xử lý.

Qua ba thuật toán trên nếu bạn hiểu được cả ba thì tức là bạn đã học xong phần kiến thứ căn bản về javascript như cách khai báo biến, vòng lặp, câu if else và cách tạo hàm rồi đấy.

Hãy để lại link bài viết gốc khi chia sẻ bài viết này, mình sẽ report DMCA với những website lấy nội dung mà không để nguồn hoặc copy bài với số lượng lớn.

Nguồn: freetuts.net

Profile photo of adminTheHalfHeart

TheHalfHeart

Có sở thích viết tuts nên đã từng tham gia viết ở một số diễn đàn, đến năm 2014 mới có điều kiện sáng lập ra freetuts.net. Sinh năm 90 và có 1 vợ 2 con, thích ca hát và lập trình.

ĐĂNG BÌNH LUẬN: Đăng câu hỏi trên Group Facebook để được hỗ trợ nhanh nhất.