30/09/2018, 17:17
Xin thuật toán tìm các số nguyên tố nhỏ hơn n
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 !!
Bài liên quan
@bigzero95 search trong diễn đàn “số nguyên tố nhỏ hơn n” sẽ thấy một số topic khác nhé.
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.
đọ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.
Số nguyên tố
Số nguyên tố là số tự nhiên chỉ có hai ước số dương phân biệt là 1 {\displaystyle 1} và chính nó. Các số có nhiều hơn 2 {\displaystyle 2} ước số dương được gọi là hợp số. Do số 1 {\displaystyle 1} chỉ có một (1) ước số dương là chính nó, nên số 1 {\displaystyle 1} không phải là số nguyên tố và cũng không phải là hợp số. C...
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...
giải thuật này trên wiki, khá hay, bạn xem thử xem thế nào