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

[TienDatPC (PC)]

Mọi người cho ý kiến để tối ưu code ạ!
Thông thường em sẽ viết hàm chạy từ 2 tới căn(a) nếu a chia hết bất kỳ số nào trong khoảng đó lập tức không phải nguyên tố.

public static boolean binhThuong(long a) {
    for (int i = 2; i <= sqrt(a); i++) {
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}

Mình viết theo thuật toán sàng số nguyên tố như sau:

public static void sangNto(int a) {
    a=a+1;
    boolean isPrime[] = new boolean[a];

    for (int i = 0; i < a; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i < a; i++) {
        if(isPrime[i]){
            for (int j = i*i; j <a; j+=i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <a; i++) {
        if(isPrime[i]){
            System.out.println(i);
        }
    }
}

[vietha0996 (Ha)]

ta chỉ cần kiểm tra a có chia hết cho một trong các số 2,3,5,7 hay không. Nếu không chia hết và a không phải 1 trong các số đó thì a cũng là số nto (a>1)

Tại sao bạn lại có giải thuật này.
Đấy là bạn mới xét tới 100 thì ra kết quả đúng chứ lấy lên 200 thì mình tìm được các số 121, 143, 169, 187 thoả mãn điều kiện của bạn nhưng nó không phải số nguyên tố.

Hơn nữa mình đọc qua đã thấy cách của bạn không đúng vì nó chỉ là 1 phần nhỏ trong điều kiện cần của phương pháp sàng nguyên tố là cách tìm nguyên tố nhanh nhất mà mình biết.

[TienDatPC (PC)]

Mình đã test lại và cũng thấy thuật toán không còn đúng với số lớn hơn 100; Bạn thường sử dụng thuật toán nào hãy post lên mình học hỏi với

[programmerit (Chi Ngo)]

Bạn chạy đến căn bậc hai của số cần kiểm tra là đúng rồi (đây là tính chất số học thôi). Còn việc bạn chọn các số để kiểm tra là tư tưởng của thuật toán có tên là sàng... mình không nhớ rõ.

[vietha0996 (Ha)]

Mình nghĩ nếu xử lí số bé thì cho i chạy từ 2 tới căn bậc hai của n là nhanh gọn rồi, còn vào những bài toán lớn, phức tạp thì dùng sàng nguyên tố hơn (bạn có thể google thêm, có rất nhiều ạ).

Sàng Eratosthenes

[nguyenhuuca (Nguyen Ca)]

Để cái hàm sqrt(a) trong vòng for là không tối ưu rồi, giả sử a lớn, sẽ tính rất nhiều lần.
Nến tính sqrt(a) ở ngoài.

[SoiLuv (Nguyễn Duy Khánh)]

Thuật toán vậy là sai r. Bạn đưa ra 4 snt đầu và thử, vậy nếu nó chia hết cho các số snt như 11, 13 thì sao ?

[Gio (Gió)]

Dùng thuật toán rabin-miller dpt O(logn).
Trong java có thư viện BigInteger có hàm kiểm tra nt sử dụng thuật toán trên:

System.out.println(BigInteger.valueOf(13331L).isProbablePrime(10));

[Do_Ngoc_The]

1 số thì dùng :số nguyên tố không chẵn ( trừ 2), không chia hết cho 3 trừ 3 là lọc được khoảng 70% hợp số , và số nguyên tố ko chia hết cho số nguyên tố trước nó ( số ngto có dạng 6k ± 1)
Còn 1 đoạn thì dùng sàng

[honghm211 (hoan_h3)]

trừ 3 là sao ạ, banj giải thích giúp minh được không ạ

[Duc_Anh_Tran (Đức Anh Trần)]

hàm này nhanh chưa ạ

bool nt(long long  m)
{
    long i1,b1=trunc(sqrt(m));
    if(m==2||m==3)
        return 1;
    if(m%2==0||m%3==0||m<2)
        return 0;
    for(i1=5; i1<=b1; i1+=6)
        if(m%i1==0||m%(i1+2)==0)
            return 0;
    return 1;
}