Bài tập Java: Tìm ước số nguyên tố nhỏ nhất của N, với N là số bất kỳ cho trước.

Bài viết này tôi sẽ hướng dẫn cách giải quyết bài tập Java cơ bản tìm ước số nguyên tố nhỏ nhất của N, với N là một số bất kỳ được cho trước.

Analyze - Phân Tích:

Bài này chúng ta cần mô tả làm rõ đề bài trước, đề yêu cầu ở đây tìm ước số nguyên tố nhỏ nhất của N, ước số nguyên tố ở đây ý muốn nói là tìm ước số của N nhưng phải là số nguyên tố nhỏ nhất.

Vậy có nghĩa là ta phải tìm số nguyên tố(là số chỉ chia hết cho 1 và chính nó) và nó phải là ước số(là một số nguyên chia hết hết của một số nguyên khác) của N.

Theo phân tích ở trên thì trước tiên ta cần tìm ước số của N, sau đó kiểm tra xem số đó có phải là số nguyên tố không? Nếu phải thì nó là ước số nguyên tố nhỏ nhất của N.


Java Source - Mã Java:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package z.test;

/**
 *
 * @author bnson
 * @website vnlives.net
 * @create 03/12/2014
 */
public class UocSoNguyenToNhoNhat {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int n = 777;
        int k;

        //Vòng for này dùng để tìm ước số của n.
        //Mà số nguyên tố nhỏ nhất luôn là 2,
        //nên ta chạy vòng for từ 2 luôn.
        for (k = 2; k <= n; k++) {

            //Kiển tra xem k có phải là ước số của n không?
            //nếu phải thì sẽ kiểm tra xem nó có phải là ước số không?
            //nếu ko phải thì sẽ kiểm tra số k tiếp theo.
            if (n % k == 0) {
               
                int dem = 0;
                //Vòng for này dùng dể xác định k có phải là ước số hay không?
                for (int x = 2; x <= k; x++) {
                   
                    //Cứ mỗi lần k chia hết cho x thì biến dem sẽ tăng 1.
                    //nếu sau khi chạy hết vòng for biến đếm bằng 1,
                    //thì nó là số nguyên tố,
                    //còn lớn hơn 1 thì không phải vì nó chia được cho số thứ 3
                    //trừ 1 và chính nó.
                    if (k % x == 0) {
                        dem++;
                    }
                   
                    //Nếu đếm lớn hơn 1 thì nó đã không còn là số nguyên tố,
                    //không cần phải tiếp tục kiểm tra.
                    if (dem > 1) {
                        break;
                    }                   
                }

                if (dem == 1) {
                    System.out.println("Uoc so nguyen to nho nhat của " + n + " la: " + k);
                    break;
                }

            }
        }
    }
}

Result - Kết Quả: