30/09/2018, 16:13
[Wiki] Hàm Kiểm Tra số nguyên tố trong C/C++
Số nguyên tố:
- Số nguyên tố là số tự nhiên chỉ chia hết cho 1 và chính nó. Ngoài ra nó không chia hết cho bất cứ số nào khác. Số 0 và 1 không được coi là số nguyên tố. - Theo wiki
-
Số 2 là số nguyên tố chẵn duy nhất.
-
Cấu trúc ở dạng C:
int soNguyenTo(int soA)
{
if (soA < 2)
return 0;
for (int i = 2; i <= sqrt((float)soA); i ++)
{
if (soA%i==0)
{
return 0;
}
}
return 1;
}
-
Định nghĩa : Do người dùng tự tạo. Có thể có nhiều cách để tối ưu.
Ví dụ : Hãy kiểm tra xem số bạn nhập có phải là 1 số nguyên tố hay không ? -
Code minh hoạ C++
#include <iostream>
using namespace std;
bool soNguyenTo(int);
bool soNguyenTo(int soA) // hàm bool trả về true/false
{
if (soA < 2) // Nếu số A nhỏ hơn 2
{
return false;// trả về false
}
else if (soA>2)// Nếu số A lớn hơn 2
{
if (soA % 2 == 0) // Xét xem A có chia hết cho 2 không?
{
return false;// Nếu chia hết, return false.
}
for (int i = 3; i < sqrt((float)soA); i += 2) // xét từ 3 đến căn bậc 2 của số A
{
if (soA%i == 0) // nếu A chia hết cho một số nào đó trong đoạn này
{
return false;// trả về kết quả sai
}
}
}
return true;// sau tất cả các chỗ trên, nó mà không sai thì cuối cùng nó đúng :3
}
int main(int argc, char ** argv)
{
int n; // khai bao so kiem tra la so nguyen
cout << "Nhap so can kiem tra?!" << endl;
cin >> n; // nhap vao so nguyen tu ban phim
if (soNguyenTo(n) == true)
{
cout << "So " << n << " la so nguyen to!!!!";
}
else
{
cout << "So " << n << " khong phai nguyen to!!!!";
}
system("pause");
return 0;
}
- Hình minh họa:
Bài liên quan
góp vui bức hình
Rút ngắn lại như trên cho dễ nhìn hơn. Các bác mới học nhìn vô cũng dễ hiểu hơn.
đang tính viết từ thô sơ tới tối ưu mà nghĩ lại cái để vậy luôn. kakaka
mình luôn dùng cách này vì mình nghĩ nó sẽ chạy nhanh hơn khi chỉ phải xét các số lẻ thay vì phải xét hết liên tiếp
for (i=3->sqrt(n), i+=2
wiki xét thế mà bạn?
Các bức hình bên trên của thuật toán sàng nguyên tố
Wow, anh còn không biết Làm vài bài ủng hộ đi @nguyenvanquan7826
nhớ không lầm là chỉ sàng được n<100
Tìm 100 thì tìm làm gì bạn
Nó dùng trong các bài toán tìm số nguyên tố trong khoảng từ a->b mà a rất nhỏ, b rất lớn, tức là khoảng cách rất lớn.
Sắp có anh ợ.
Vừa lúc sáng viết lại thử cái sàng nguyên tố
chuẩn men kakakakaka
Đa số e thấy mn toàn dùng cách là xét chia hết cho các số lẻ từ 3 -> sqrt(n).
Và thấy nhiều người bảo là tối ưu nhất
Các SNT trừ 2 và 3 ra để có dạng (6k + 1) hoặc (6k - 1)
Code C++
Có gì sai sót mong mn chỉ bảo
Tại sao phải xét từ 2 đến căn bậc hai của số A
tai sao chạy từ 2- sqrt(A)
dễ dàng chứng minh nếu A là hợp số thì sẽ có ít nhất 1 ước #1 <=sqrt(A)
bởi nếu tất cả các ước #1>sqrt(A) thì ước1 * ươc2 … >A
ukm, thanks
Đa số hiện nay người ta sử dung đơn giản ý tưởng như Nguyễn Duy Khánh, đó là ý tưởng bước nhảy 2, 4 so le với nhau, có nhiều cách viết nhưng ý tưởng là vậy
cái đoạn này ai giải thích trình tự hđ của nó dc k
bai tren co loi cho n=9.