CĂN BẢN
DOM & BOM
XỨ LÝ FORM
JAVASCRIPT TIPS
TUTORIALS
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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

Trong bài này freetuts.net sẽ hướng dẫn cách kiểm tra số nguyên tố javascript bằng ba cách khác nhau., qua đó giúp bạn biết được thuật toán kiểm tra SNT dễ dàng.

Để làm được bài này thì bạn phải biết các kiến thức về khai báo biến, vòng lặp for, functionlệnh if else, đó là kiến thức nền tảng cơ bản nhất để bạn có thể làm các bài tập javascript.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Trước khi vào phần bài giải thì bạn xem qua khái niệm số nguyên tố đã nhé, nếu không bạn sẽ không biết được hướng giải.

1. Cách 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ố.

Demo RUN
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. Cách 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.

Demo RUN
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. Cách 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).

Demo RUN
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, tài vì với những 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ý.

Cùng chuyên mục:

Cách gộp hai object javascript lại với nhau

Cách gộp hai object javascript lại với nhau

Cách lấy chiều dài của object trong Javascript

Cách lấy chiều dài của object trong Javascript

Hướng dẫn giải phương trình bậc 1 bằng Javascript

Hướng dẫn giải phương trình bậc 1 bằng Javascript

Cách dùng nextSibling trong javascript

Cách dùng nextSibling trong javascript

Cách dùng insertAdjacentHTML trong javascript

Cách dùng insertAdjacentHTML trong javascript

Cách dùng innerHTML trong Javascript

Cách dùng innerHTML trong Javascript

Cách dùng insertBefore trong javascript

Cách dùng insertBefore trong javascript

Cách dùng insertAfter trong Javascript

Cách dùng insertAfter trong Javascript

Cách dùng parentNode trong Javascript

Cách dùng parentNode trong Javascript

Cách dùng parentElement trong Javascript

Cách dùng parentElement trong Javascript

Tính tổng các phần tử trong mảng javascript

Tính tổng các phần tử trong mảng javascript

Tính tổng hai số bằng Javascript (cộng hai số)

Tính tổng hai số bằng Javascript (cộng hai số)

Cách gán giá trị cho thẻ input trong javascript

Cách gán giá trị cho thẻ input trong javascript

Để gán giá trị cho thẻ input thì ta có hai cách, thứ nhất là…

Cách kiểm tra số nguyên âm trong javascript

Cách kiểm tra số nguyên âm trong javascript

Cách kiểm tra số nguyên dương trong javascript

Cách kiểm tra số nguyên dương trong javascript

Hàm closure trong javascript

Hàm closure trong javascript

Closure là một khái niệm không phải ai cũng ..

Biểu thức chính quy RegEx trong Javascript

Biểu thức chính quy RegEx trong Javascript

Bài này chúng ta sẽ tìm hiểu đến chuỗi và cách sử dụng biểu thức…

Cách dùng Import / Export Module trong javascript

Cách dùng Import / Export Module trong javascript

Khi bạn xây dựng một ứng dụng nhỏ thì việc đặt

Cơ chế hoạt động của hoisting trong Javascript

Cơ chế hoạt động của hoisting trong Javascript

Hoisting là vấn đề liên quan đến cách khai báo biến trong Javascript. Nó liên…

Cấp độ private / protected của class trong Javascript

Cấp độ private / protected của class trong Javascript

Top