30/09/2018, 18:19
Thuật toán kiểm tra số nguyên tố tối ưu
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); } } }
Bài liên quan
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.
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
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õ.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 ạ).
vi.wikipedia.org
Sàng Eratosthenes
Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) "phát minh" ra. Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.[cần dẫn nguồn] Để tìm các số nguyên tố nhỏ hơn hoặc bằng...
Để 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.
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 ?
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:
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