Kiểm tra số nguyên tố bằng Javascript

Đăng bởi: TheHalfHeart - Vào ngày: - View: 22091

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ến, vò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.

Khóa học nên xem

Nguồn: freetuts.net