Kiểm tra số nguyên tố?

#1

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;
 }
1 Like
#2

Thì bạn run rồi test và con số, nếu được thì ok :smiley: Search Google bảng số nguyên tố dưới 10000 ấy :smiley:

Nói chung thì cách nhanh nhất là dùng return false và return true cũng được :slight_smile:

Nếu theo Google nói thì như thế này

for (int i = 3; i <= sqrt(n); i+=2)
{
       if (n%i == 0)
               return false;
} 
return true;

Đại loại là như thế, mình code liền tay nên chưa kiểm tra kỹ :slight_smile:

Mà dùng kiểu dữ liệu bool nha, nếu không thì dùng _Bool cũng được nhưng thay return false thành return 0 và return true thành return 1

1 Like
#3

em 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 :frowning: em chỉ sợ code em sai thui chứ nhìn là biết cách xài bool nhanh hơn rồi :smiley:

1 Like
#4

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.

1 Like
#5

Mình nhìn sơ qua thì cũng thấy chính xác đó vì thuật toán cũng hay :slight_smile:
Nếu không yên tâm thì kiểm tra một vài số lớn thôi :slight_smile:

VD:
Số nguyên tố: 5573 ; 6301 ; 7919 ; 4421 ; …
Hop so: Các số còn lại, tùy bạn :slight_smile:

P/S: Mà code của bạn markdown bị lỗi rồi

1 Like
#6

thanks các bác :smiley: em cũng check vài số lớn rồi vẫn ổn :smiley: em thông rồi :grin:

#7

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ỗi :slight_smile:

1 Like
#8

thanks bác em quên mất :v

1 Like
#9

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 :smile:

1 Like
#10

nhưng mà chưa có cái em cần tìm nên mới lập cái mới :smiley:

1 Like
#11

Cách này đúng nhưng mà chưa tối ưu :smiley:

1 Like
#12

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

1 Like
#13

thanks bác cảm giác nhanh hơn thiệt :smiley:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?