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

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

#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 …

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)

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.

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

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