30/09/2018, 21:06
Kiểm tra số nguyên tố?
lúc đâu em viết cái này là chưa google thì em nghĩ là số nguyên tố là số chia hết cho 1 và chính nó nghĩa là ước chung của nó chỉ có 1 và chính nó nên em làm như thế này nhưng sau khi lên google thì thấy hầu hết là toàn dùng cho i chạy từ 2 tới căn 2 nên em cũng không biết cách này của em có đúng không :(( ae giải thích cho em với :((
#include <iostream>
using namespace std;
int main(){
//khaibao
int n = 0 ,i,tong = 0;
//nhap
cout << "chuong trinh kiem tra so nguyen to"<<endl;
cout << "nhap vao so can kiem tra : ";
cin >> n;
//giaithuat
for(i = 1;i <= n; ++i){
if (n % i ==0){
tong = tong +i;
}
}
if (n+1 == tong){
cout << n <<" la mot so nguyen to "<<endl;
}
else {
cout <<n << " khong phai la mot so nguyen to"<<endl;
}
return 0;
}
Bài liên quan
Thì bạn run rồi test và con số, nếu được thì ok Search Google bảng số nguyên tố dưới 10000 ấy
Nói chung thì cách nhanh nhất là dùng
return falsevàreturn truecũng đượcNếu theo Google nói thì như thế này
Đại loại là như thế, mình code liền tay nên chưa kiểm tra kỹ
Mà dùng kiểu dữ liệu
boolnha, nếu không thì dùng_Boolcũng được nhưng thayreturn falsethànhreturn 0vàreturn truethànhreturn 1em test thì oke chưa test full đc cả dưới 10000 số mà dưới 200 thì chưa sai phát nào nên em mới thắc mắc :’(
kiểu xài bool em chạy rồi em chỉ sợ code em sai thui chứ nhìn là biết cách xài bool nhanh hơn rồi
về thuật toán thì đúng rồi, còn tối ưu thì cách chạy tới sqrt(n) tối ưu hơn. Dù sao tự nghĩ ra thuật toán cũng rất tốt.
Mình nhìn sơ qua thì cũng thấy chính xác đó vì thuật toán cũng hay
Nếu không yên tâm thì kiểm tra một vài số lớn thôi
VD:
Số nguyên tố: 5573 ; 6301 ; 7919 ; 4421 ; …
Hop so: Các số còn lại, tùy bạn
P/S: Mà code của bạn markdown bị lỗi rồi
thanks các bác em cũng check vài số lớn rồi vẫn ổn em thông rồi
Mà quên mất, bạn nên xét thêm trường hợp
if (n == 0) ...nữa nhé, không là lỗithanks bác em quên mất :v
Bạn có thể tìm theo từ khóa “số nguyên tố”. Trên diễn đàn cũng đã có nhiều topic nói về thằng này
nhưng mà chưa có cái em cần tìm nên mới lập cái mới
Cách này đúng nhưng mà chưa tối ưu
Cách nghĩ này thú vị, nhưng chạy chậm và có thể cải tuến được.
Vd: đoạn chia cho i, nếu cho i chạy từ 1 -> (n-1) thì có thể dừng và kết luận ngay khi có n % i == 0 (vì chia hết 1 số khác 1 và khác n tức n là hợp số). Muố kết luận nhanh hơn thì xài từ 1 _-> căn n.
Nhưng minhf thấy cách nghĩ thuạt toán rất hay.
Btw khi làm các bài tính tonas lớn mình dùng sàng nguyên tố.
thanks bác cảm giác nhanh hơn thiệt