Thuật toán viết hàm kiểm tra số nguyên tố trong php

Nếu bạn đang học php và đang tìm cách để kiểm tra một số có phải là số nguyên tố hay không thì đây là bài viết hữu ích cho bạn. Trong bài này tôi chia sẻ về thuật toán và cách cài đặt chương trình từng bước.

Số nguyên tố là gì?

Các số nguyên tố là các số tự nhiên lớn hơn 1 và không phải là tích của hai số tự nhiên nhỏ hơn.

Theo Wiki

Hay nói cách khác, số n được gọi là số nguyên tố khi nó chỉ chia hết cho 1 và chính nó.

Chú ý: Số nguyên tố là một phần rất quan trọng trong việc xây dựng các hệ thống mã hóa cao cấp vì chính từ sự phức tạp tính toán để tìm ra một số nguyên tố lớn.

Các số nguyên tố từ 2 đến 100

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.

Thuật toán kiểm tra số nguyên tố

Như định nghĩa số nguyên tố để kiểm tra xem một số chúng ta cần kiểm tra số ước của nó. Nếu tồn tại ít nhất một ước k nào đó với 1 < k < n thì kết luận ngay k không phải số nguyên tố mà không cần kiếm tra thêm.

Một điều quan trọng trong toán học. Nếu n có một ước là k thì sẽ tồn tại một ước m nào đó để n = k*m.

Một điều quan trọng nữa n = √n * √n nên chúng ta chỉ cần kiểm tra ước từ 2 đến √n là đủ điều kiện để kết luận. Bởi vì, nếu không tổn tại một số k trong khoảng (2, √n) thì không thể tồn tại một số m trong khoảng (√n, n - 1) để thoải mãn điều kiện n = k*m.

Cài đặt chương trình kiểm tra số nguyên tố

<?php
function check_prime($n)
{
    for ($i = 2; $i <= sqrt($n); $i++) {
        if ($n % $i == 0){
            return false;
        }
    }
    return true;
}
$n = 101;
if(check_prime($n))
    echo "{$n} là số nguyên tố";
else
    echo "{$n} là hợp số";

Kết quả sau khi chạy chương trình

 101 là số nguyên tố 

Với n = 50 ta có kết quả

50 là hợp số

Tìm danh sách các số nguyên tố trong một khoảng cho trước

Khi đã hoàn thành việc kiểm tra một số có phải là sô nguyên tố hay không thì việc liệt kê nó trong một khoảng cho trước rất dễ dàng.

Chúng ta tạo thêm hàm show_prime($a, $b). Trong quá trình xử lý dữ liệu sẽ gọi hàm check_prime() để kiểm tra. Nếu là số nguyên tố ngay lập tức xuất lên màn hình.

<?php
function check_prime($n)
{
    for ($i = 2; $i <= sqrt($n); $i++) {
        if ($n % $i == 0){
            return false;
        }
    }
    return true;
}

function show_prime($a, $b){
    for ($i = $a; $i <= $b; $i++){
        if(check_prime($i))
            echo $i, '<br>';
    }
}

show_prime(25, 60);

Chạy code trên ta có danh sách các số nguyên tố từ 2 đến 50

29
31
37
41
43
47
53
59

Tổng kết

Trong bài này tôi đã hướng dẫn bạn cách để kiểm tra số nguyên tố và tìm danh sách một số nguyên tố trong một khoảng cho trước. Đây là một bài toán khá điểm hình để luyện kỹ năng code và kỹ năng tư duy mức cơ bản.

Việc của bạn ngay bây giờ hãy đọc lại kỹ thuật toán và bắt đầu cài đặt lại chương trình để nắm chắc bài học.

Xin chào, sớm hẹn gặp lại!