CĂN BẢN
DOM & BOM
XỨ LÝ FORM
JAVASCRIPT TIPS
TUTORIALS
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

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.

Để 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.

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ố.

Bài viết này được đăng tại [free tuts .net]

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:

Functional Programming là gì? Tại sao và khi nào bạn nên sử dụng trong JavaScript

Functional Programming là gì? Tại sao và khi nào bạn nên sử dụng trong JavaScript

Những tính năng mới trong ES6+ trong JavaScript

Những tính năng mới trong ES6+ trong JavaScript

4 cách tránh memory leaks trong JavaScript

4 cách tránh memory leaks trong JavaScript

Capturing và bubbling Event trong Javascript

Capturing và bubbling Event trong Javascript

Phân biệt prototype và __proto__ trong JavaScript

Phân biệt prototype và __proto__ trong JavaScript

Cách hoạt động của Event Loop trong JavaScript

Cách hoạt động của Event Loop trong JavaScript

Phương thức bind(), call(), và apply() trong JavaScript

Phương thức bind(), call(), và apply() trong JavaScript

Cách khắc phục lỗi

Cách khắc phục lỗi "hoisting" trong JavaScript

Sử dụng Promise.all và Promise.race để quản lý các Promise trong JavaScript

Sử dụng Promise.all và Promise.race để quản lý các Promise trong JavaScript

Xử lý bất đồng bộ bằng vòng lặp for-await trong JavaScript

Xử lý bất đồng bộ bằng vòng lặp for-await trong JavaScript

Sự khác biệt giữa Promise, Callback và Async/Await trong JavaScript

Sự khác biệt giữa Promise, Callback và Async/Await trong JavaScript

Cách sử dụng Async functions trong JavaScript

Cách sử dụng Async functions trong JavaScript

Hàm String isspace() trong Python

Hàm String isspace() trong Python

Cách tạo số ngẫu nhiên trong Javascript

Cách tạo số ngẫu nhiên trong Javascript

Hướng dẫn cách tạo một số ngẫu nhiên ...

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

Top