Em đang có bài tập viết chương trình nhập vào số nguyên n sau đó tìm và in ra các số nguyên tố nhỏ hơn n .Mong mọi người giúp em giải thuật !!
Xin thuật toán tìm các số nguyên tố nhỏ hơn n
dạ .em cần anh giúp em giải thuật ạ. !!
số nguyên tố là số lớn hơn 1, chỉ chia hết cho 1 và chia hết cho chính nó, dùng các câu lệnh if else thôi
có phải là dùng vòng lặp cho i chạy từ 2 đến i< n .Rồi lấy n chia cho i .số nào không chia hết là số đó là số nguyên tố không ạ @@
Khi kiểm tra có phải là số nguyên tố không thì chỉ cần cho chạy đến căn bậc 2 của n để kiểm tra thôi, không cần phải chạy đến n - 1.
1 Like
đọc tiêu đề mình tưởng n!, nếu vậy đây cũng là 1 vấn đề thú vị (nhưng chắc vẫn lấy căn của n! thôi, vì số nguyên tố vẫn có thể chạy đến sát căn n! mà -_- )
n! nó chẳng khác gì n, khi nhập vào thì nó là hằng số, mình chỉ cần dùng thêm 1 biến để tính và lưu giá trị của n! thôi.
- Độ phức tạp O(n*sqrt(n)) thì tính đến căn
- Độ phức tạp O(nlog(n)) thì dùng rabin-miller để kiểm tra
- Độ phức tạp O(n loglogn) thì dùng sieve of Eratosthenes, trên diễn đàn cũng có 1 số bài viết sàng nguyên tố và ứng dụng
- Độ phức tạp O(n) thì dùng sieve of Atkin . Mình cũng viết 1 code tham khảo tại đây
3 Likes
giải thuật này trên wiki, khá hay, bạn xem thử xem thế nào
1 Like