Category: Uncategorized

Một số thuật toán cơ bản xung quanh số nguyên tố – Java

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số kiến thức cơ bản xung quanh số nguyên tố.

Một số tự nhiên p (p > 1) là số nguyên tố nếu p có đúng 02 ước số là 1 và p.

Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, …

Chúng ta cùng nhau thực hiện một số giải thuật cơ bản bằng ngôn ngữ Java để giải quyết các bài toán con sau:

  • Kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không.
  • Liệt kê các số nguyên tố nằm trong phạm vi [1, n].

Kiểm tra tính nguyên tố

Giải thuật thứ nhất

Ý tưởng giải thuật

Chúng ta kiểm tra xem có tồn tại một số nguyên k (2 ≤ k ≤ n – 1) mà k là ước của n (n chia hết cho k) thì n không phải là số nguyên tố, ngược lại n là số nguyên tố.

Trên thực tế ta chỉ cần kiểm tra k từ 2 đến √n là được.

Bước 1.

Chúng ta tạo một Java Project trong Eclipse IDE và đặt tên là JavaAlgorithmBasicProject.

Chúng ta tiếp tục tạo package main và class Main.java cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithm và class SoNguyenTo.java.

Chúng ta tiếp tục tạo phương thức kiemTraSNTFirst() với:

  • Tham số cho phương thức này là một số tự nhiên n.
  • Kiểu dữ liệu trả về là boolean. Phương thức trả về kết quả: (i) true nếu n là số nguyên tố; (ii) false nếu ngược lại.

Bước 3.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Phương thức để tính căn bậc 2 của một số tự nhiên n là Math.sqrt().
  • Phương thức để lấy phần nguyên của một số thập phân là Math.round().
  • Thư viện Math định nghĩa các phương thức dùng tính toán các biểu thức toán học cơ bản. Các phương thức này đều là tĩnh nên được gọi trực tiếp bằng cú pháp Math.phương_thức().

Bước 4.

Chúng ta thực hiện thử nghiệm phương thức kiemTraSNTFirst() trong class Main.java như sau:

Bước 5.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Giải thuật thứ hai

Ý tưởng giải thuật

Chúng ta sẽ chỉ kiểm tra các số k có tính chất giống với một trong hai tính chất cơ bản sau của số nguyên tố:

  • Trừ số 2 và các số nguyên tố là số lẻ.
  • Trừ số 2, 3, các số nguyên tố có dạng 6k ± 1 (vì số có dạng 6k ± 2 thì chia hết cho 2, số có dạng 6k ± 3 thì chia hết cho 3).

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức kiemTraSNTSecond() trong class Main.java như sau:

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Liệt kê các số nguyên tố trong đoạn [1, N]

Giải thuật thứ nhất

Ý tưởng giải thuật

Chúng ta lần lượt xem xét các số m trong đoạn [1, n], rồi kiểm tra tính nguyên tố của m.

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Java cung cấp cho chúng ta một số kiểu dữ liệu lưu trữ tập hợp các phần tử bên cạnh kiểu dữ liệu mảng. Chúng ta thường sử dụng một số dạng sau: (i) List để lưu trữ không giới hạn các phần tử có thể trùng nhau; (ii) Set để lưu trữ không giới hạn các phần tử không trùng nhau; (ii) Map để lưu trữ không giới hạn các phần tử theo từng cặp . Chúng ta sẽ dần tìm hiểu cụ thể hơn trong những bài tiếp theo.
  • Java cung cấp một phương pháp để xác định kiểu dữ liệu cho toàn bộ các phần tử trong danh sách: định nghĩa ngay từ ban đầu kiểu dữ liệu trong cặp dấu <>. Ví dụ ở đây là List.
  • Với tham số là một biến riêng lẻ, giá trị của tham số sẽ không bị thay đổi sau khi thực hiện phương thức.
  • Với tham số là một danh sách, các phần tử của danh sách có thể bị thay đổi sau khi thực hiện phương thức.

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức lietKeSNTFirst() trong class Main.java như sau:

Những kỹ thuật lập trình cần chú ý:

  • Java cung cấp các dạng List khác nhau để chúng ta sử dụng tùy theo trường hợp: (i) ArrayList được sử dụng khi không quan tâm đến thứ tự trước sau của các phần tử; (ii) LinkedList được sử dụng khi quan tâm đến thứ tự trước sau của các phần tử.
  • Kiểu dữ liệu của các phần tử trong List đã được khai báo ban đầu thì không cần khai báo đối với ArrayList<>.
  • Số lượng phần tử của một danh sách là không giới hạn nên không cần khai báo trước số lượng phần tử ban đầu.

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Giải thuật thứ hai

Ý tưởng giải thuật

Chúng ta áp dụng sàng Eratosthenes (https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes ) để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên n:

  • Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,…, n).
  • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
  • Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
  • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

Bước 1.

Chúng ta thực hiện giải thuật bằng ngôn ngữ Java như sau:

Bước 2.

Chúng ta thực hiện thử nghiệm phương thức lietKeSNTSecond() trong class Main.java như sau:

Bước 3.

Chúng ta thực thi toàn bộ project để kiểm tra kết quả thử nghiệm:

Tổng kết

Trong bài này, chúng ta đã cùng nhau tìm hiểu một số giải thuật cơ bản xung quanh số nguyên tố và thực hiện bằng ngôn ngữ Java.

Hy vọng rằng chúng ta có thể áp dụng phù hợp những kỹ thuật và chức năng này cho những bài tiếp theo.

Cấu hình thông dịch và Xây dựng chương trình Python đầu tiên trên Eclipse IDE

Giới thiệu

Trong bài này, chúng ta cùng nhau xây dựng chương trình Python đầu tiên trên Eclipse IDE.

Tương tự như các chương trình lập trình đầu tiên với các ngôn ngữ khác, nội dung chính của chương trình này:

  • Cấu hình thông dịch và thực thi các chương trình Python trên Eclipse IDE.
  • Hiển thị ra màn hình Console câu tiếng Việt “Xin chào thế giới lập trình và ngôn ngữ Python”.

Cấu hình thông dịch Python

Bước 1.

Chúng ta khởi động Eclipse IDE và lựa chọn thư mục chứa các dự án.

Ví dụ ở đây chúng ta lựa chọn thư mục EclipseIDE.

/home/homes/Documents/GocHocTap/EclipseIDE

Chúng ta lựa chọn nút Launch để tiếp tục.

Hình 1. Khởi động Eclipse IDE và lựa chọn workspace.

Bước 2.

Màn hình chính của Eclipse IDE sẽ hiện ra bao gồm các phân vùng khác nhau.

Chúng ta lựa chọn chức năng Window → Preferences để thực hiện cấu hình thông dịch Python.

Hình 2. Lựa chọn Window -> Preferences để thực hiện cấu hình thông dịch.

Bước 3.

Màn hình Preferences hiện ra.

Chúng ta lựa chọn mục PyDev → Interpreters → Python Interpreter trong phân vùng bên trái.

Chúng ta lựa chọn nút Browse for python/pypy exe trong phân vùng bên phải để tiếp tục.

Hình 3. Lựa chọn Python Interpreter.

Bước 4.

Màn hình Select Interpreter hiện ra.

Chúng ta nhập các thông tin tương tự như sau:

Interpreter Name: python36

Interpreter Executable: /home/homes/anaconda3/envs/PythonCPU/bin/python3.6

Những điểm cần chú ý:

  • Tên thông dịch. Chúng ta có thể đặt tên tùy ý.
  • Đường dẫn đến tập tin thực thi. Chúng ta tham khảo các bài viết trên blog GocHocTap về thiết lập các thư viện cho Python bằng Anaconda. Chúng ta tạo môi trường Python mới, ví dụ ở đây là PythonCPU. Như vậy tập tin python3.6 nằm trong thư mục PythonCPU/bin.

Chúng ta lựa chọn nút OK để thực hiện tạo thông dịch Python mới.

Hình 4. Lựa chọn đường dẫn đến python3.6.

Bước 5.

Màn hình tổng hợp các thư viện cơ bản của Python hiện ra.

Chúng ta lựa chọn hết các mục.

Chúng ta lựa chọn nút OK để tiếp tục.

Hình 5. Màn hình tổng hợp các thư viện cơ bản khi lựa chọn python3.6.

Bước 6.

Màn hình Preferences tổng hợp các thư viện sau khi lựa chọn thông dịch Python.

Chúng ta lựa chọn nút Apply and Close để áp dụng.

Hình 6. Màn hình Preferences tổng hợp tất cả thư viện sau khi lựa chọn python3.6.

Bước 7.

Eclipse IDE thực hiện áp dụng thông dịch Python được thiết lập.

Hình 7. Eclipse IDE thực hiện áp dụng thông dịch Python mới.

Xây dựng chương trình Python đầu tiên

Bước 1.

Trong màn hình chính của Eclipse IDE.

Chúng ta lựa chọn chức năng File → New → Other để tạo dự án mới.

Hình 8. Lựa chọn tạo dự án mới.

Bước 2.

Màn hình New hiện ra.

Chúng ta lựa chọn PyDev → PyDev Project để tạo dự án Python mới.

Chúng ta lựa chọn nút Next > để tiếp tục.

Hình 9. Lựa chọn tạo dự án PyDev mới.

Bước 3.

Màn hình PyDev Project hiện ra.

Chúng ta nhập các thông tin như sau:

Project name: PythonHelloWorld

Các lựa chọn khác để mặc định.

Chúng ta lựa chọn nút Finish để thực hiện tạo dự án mới.

Hình 10. Nhập thông tin dự án PyDev mới.

Bước 4.

Màn hình thông báo hiện ra, hỏi chúng ta có muốn chuyển sang giao diện của PyDev hay không.

Chúng ta lựa chọn nút Open Perspective để thực hiện việc chuyển sang giao diện mới.

Hình 11. Lựa chọn giao diện của PyDev trong Eclipse IDE.

Bước 5.

Màn hình giao diện của PyDev hiện ra.

Chúng ta có thể nhìn thấy phân vùng bên góc trái màn hình có thể hiện cấu trúc thư mục của dự án PythonHelloWorld.

Hình 12. Giao diện PyDev trong Eclipse IDE.

Bước 6.

Chúng ta nhấn chuột phải vào tên dự án PythonHelloWorld.

Chúng ta lựa chọn New → Source Folder để tạo thư mục lưu trữ mã nguồn.

Hình 13. Lựa chọn tạo thư mục lưu trữ mã nguồn Python.

Bước 7.

Màn hình Create a new Source Folder hiện ra.

Chúng ta nhập các thông tin tương tự như sau:

Project: PythonHelloWorld

Name: src

Chúng ta lựa chọn nút Finish để thực hiện.

Hình 14. Nhập thông tin thư mục lưu trữ mã nguồn Python.

Bước 8.

Màn hình giao diện của PyDev hiện ra sau khi tạo thư mục src.

Chúng ta nhấn chuột phải vào thư mục src.

Chúng ta lựa chọn New → PyDev Module để tạo tập tin Python mới.

Hình 15. Lựa chọn tạo tập tin Python mới.

Bước 9.

Màn hình Create a new Python module hiện ra.

Chúng ta nhập các thông tin tương tự như sau:

Source Folder: /PythonHelloWorld

Package: src

Name: Main

Chúng ta lựa chọn nút Finish để thực hiện.

Hình 16. Nhập thông tin tập tin Python mới.

Bước 10.

Màn hình lựa chọn template cho tập tin Python hiện ra.

Chúng ta lựa chọn template:

Module: Main

Chú ý rằng đây là tập tin chính để thực thi chương trình nên chúng ta lựa chọn template này.

Chúng ta lựa chọn nút OK để thực hiện.

Hình 17. Lựa chọn template cho tập tin Python mới.

Bước 11.

Màn hình giao diện của PyDev hiện ra sau khi tạo tập tin Main.py.

Chúng ta nhận thấy tập tin Main.py đã được mở tự động.

Chúng ta thực hiện đoạn mã nguồn để hiển thị ra các câu trên màn hình Console với các chuỗi lệnh như trong hình.

Những điểm cần chú ý theo quy định trong Python:

  • Các dòng mã nguồn trên được viết bên trong phương thức chính __main__.
  • Phương thức để hiển thị một thông tin ra màn hình Console là print().
  • Do hiển thị 02 câu nên ở đây chúng ta áp dụng một phương pháp là viết 02 lần phương thức print().
Hình 18. Mã nguồn cho tập tin Main.py.

Bước 12.

Chúng ta thực hiện cấu hình thực thi chương trình.

Chúng ta lựa chọn Run → Run Configurations… .

Hình 19. Lựa chọn cấu hình thực thi chương trình Python.

Bước 13.

Màn hình Run Configurations hiện ra.

Chúng ta nhấn đôi chuột vào mục Python Run trong phân vùng bên trái để tạo cấu hình mới.

Chúng ta nhập các thông tin tương tự như sau:

Name: PythonHelloWorld

Project: PythonHelloWorld

Main Module: Main.py

Chúng ta lựa chọn nút Run để áp dụng và thực thi chương trình.

Hình 20. Nhập thông tin cấu hình thực thi chương trình Python.

Bước 14.

Màn hình giao diện của PyDev hiện ra sau khi tạo thực thi chương trình PythonHelloWorld.

Chúng ta nhận thấy màn hình Console trong phân vùng bên dưới đã hiển thị các câu tiếng Việt theo đúng như trong mã nguồn.

Hình 21. Màn hình Console hiển thị thông tin như trong mã nguồn.

Bước 15.

Đối với những lần thực thi tiếp theo.

Chúng ta lựa chọn mũi tên hướng xuống ngay bên cạnh nút mũi tên màu xanh trên thanh Toolbars.

Chúng ta lựa chọn chức năng 1 PythonHelloWorld.

Hình 22. Lựa chọn thực thi PythonHelloWorld.

Tổng kết

Trong bài này chúng ta đã cùng nhau thực hiện những công việc chính sau:

  • Cấu hình thông dịch Python trong Eclipse IDE.
  • Thiết lập một dự án PyDev bằng Eclipse IDE.
  • Tìm hiểu một số đoạn mã nguồn Python cơ bản để hiển thị thông tin ra màn hình Console.
  • Cấu hình Eclipse IDE để thực thi chương trình.