Xin thuật toán tìm các số nguyên tố nhỏ hơn n

[bigzero95 (BigZero)]

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 !!

[ltd (Lê Trần Đạt)]

@bigzero95 search trong diễn đàn “số nguyên tố nhỏ hơn n” sẽ thấy một số topic khác nhé.

Tính tổng các số nguyên tố nhỏ hơn n ( đk 0>tong>120)

#include <iostream> using namespace std; int main(int argc, char **argv) { int n; nhaplaidipanoi: cout << "nhap gia tri n: " << endl; cin >> n; while (n <3) { goto nhaplaidipanoi; } int temp = n; int tong = 0; for (int i = 3; i < sqrt(temp); i++) { if (i % 2 != 0) { cout << "so nay la so nguyen to : " << i << endl; tong += i; } if (tong > 0 && tong < 120) { cout << "so n …

In các số nguyên tố nhỏ hơn N chỉ dùng đệ quy

anh đạt ơi?em đang có một bài tập mà k piết sử lí thuật tuán kiểu j? Đề là viết hàm Xây dựng chương trình C cho phép nhập vào một số và in ra các số nguyên tố nhỏ hơn số vừa nhập Điều khó là yêu cầu bài tập là dùng hàm đại quy để sử lí bài toán(k dùng vòng lặp)

[bigzero95 (BigZero)]

dạ .em cần anh giúp em giải thuật ạ. !!

[yuh (Huy)]

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

[bigzero95 (BigZero)]

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 ạ @@

[iamz]

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.

[Tulip (lx)]

đọ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à -_- )

[iamz]

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.

[Gio (Gió)]

• Độ 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

[xuantoi (hn1142)]

Số nguyên tố

Sàng Eratosthenes

giải thuật này trên wiki, khá hay, bạn xem thử xem thế nào