Trang 1 trên tổng số 8 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 77 kết quả

Đề tài: Thuật toán tìm số nguyên tố?

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    153

    Unhappy Thuật toán tìm số nguyên tố?

    Hix giáo viên cho mình bài tập nhập một số và tìm xem nó có phải là số nguyên tố không? mình đã thử làm nhưng mãi không nghĩ ra được cách làm bạn nào biết có thể giúp mình với mình dốt toán quá không nghĩ ra được.Mình xin cảm ơn rất nhiều.
    Đã được chỉnh sửa lần cuối bởi comeonbaby : 23-11-2007 lúc 09:27 PM.

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    Trích dẫn Nguyên bản được gửi bởi comeonbaby Xem bài viết
    Hix giáo viên cho mình bài tập nhập một số và tìm xem nó có phải là số nguyên tố không? mình đã thử làm nhưng mãi không nghĩ ra được cách làm bạn nào biết có thể giúp mình với mình dốt toán quá không nghĩ ra được.Mình xin cảm ơn rất nhiều.
    hihi newbie hả:
    số nguyên tố là số chỉ chia hết cho 1 và chính nó.

    C Code:
    1. int KTNguyenTo(int n)
    2. {
    3.     if(n==1 || n==2) return 1;
    4.     for(int i=2; i<n/2; i++)
    5.     {
    6.         if(n%i==0) return 0;
    7.     }
    8.     return 1;
    9. }

  3. #3
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,721

    C Code:
    1. int KTNguyenTo(int n)
    2. {
    3.     //if(n==1 || n==2) return 1; //Bỏ dòng này đi
    4.     for(int i=2; i<=sqrt(n); i++) //Theo Dr thì chỗ này phải sửa lại như thế này.
    5.     {
    6.         if(n%i==0) return 0;
    7.     }
    8.     return 1;
    9. }

    Bài này khá đơn giản, Dr thấy trên cộng đồng C Việt có rất nhiều đề tài thảo luận về cái này.
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  4. #4
    Ngày gia nhập
    11 2007
    Bài viết
    153

    cám ơn các bạn rất nhiều nhưng mình vẫn chưa hiểu đoạn cấu trúc for
    f(n==1 || n==2) return 1;
    for(int i=2; i<=sqrt(n); i++)
    {
    if(n%i==0) return 0;
    ở đây khi nhập n =5 chẳng hạn thì cấu trúc for sẽ kiểm tra với i=2 đầu tiên lấy căn của 5/2 rồi tiếp tục tăng i lên cho đến bao giờ = căn của 5 thì thôi nếu vẫn không chia hết thì trả về là số nguyên tố còn nếu chia hết thì trả về là không fải là số nguyên đúng không? vậy lệnh return 0 nằm trong for tại sao lại không dc chạy khi cấu trúc bị lặp như vậy nếu mình để code như thế này thì sao?
    #include <stdio.h>
    #include <conio.h>
    #include <math.h>

    void main()
    {

    int a,b,c;
    clrscr();
    printf("\n nhap so can tim co phai nguyen to: ");

    scanf("%d",&a);

    for (b=2;b<=sqrt(a);b++)
    { if( a%b==0)
    { printf("\n day khong phai la so nguyen to");// ở đây lệnh printf có được lặp đi lặp lại không?? quả thật mình không hiểu về các lệnh trong cấu trúc for được thực hiện như thế nào lên ko biết mong các bạn giúp cho :(( hix học mãi vẫn chẳng hiểu gì ngu quá

    }
    else if (a%b!=0)

    {
    printf("\n day la so nguyen to");
    }}
    getch();
    Đã được chỉnh sửa lần cuối bởi comeonbaby : 23-11-2007 lúc 09:34 PM.

  5. #5
    Ngày gia nhập
    10 2007
    Nơi ở
    /root
    Bài viết
    318

    Thuật toán chuẩn :

    C Code:
    1. bool CheckNguyenTo(int n)
    2. {
    3.      if(n == 2 || n == 3)
    4.      {
    5.          return true;
    6.      }
    7.      if( n == 1 || n == 2 || n % 2 == 0 || n % 3 == 0)
    8.      {
    9.          return false;
    10.      }
    11.      if( n < 25 )
    12.      {
    13.          return true;
    14.      }
    15.      int i = 5 ;
    16.      int j = 2 ;
    17.      while(i <= floor(sqrt(n)))
    18.      {
    19.              if(n % i == 0 )
    20.              {
    21.                   return false;
    22.                   break;
    23.              }
    24.              else
    25.              {
    26.                 i = i + j ;
    27.                 j = 6 - j ;
    28.                 return true;
    29.              }
    30.      }  
    31. }

  6. #6
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Mặc định Thuật toán tìm số nguyên tố?

    Trích dẫn Nguyên bản được gửi bởi void main () Xem bài viết
    Thuật toán chuẩn :

    C Code:
    1. if(n % i == 0 )
    2. {
    3.     return false;
    4.     break;
    5. }
    Xin hỏi return rồi thì có phải break; nữa không?
    Còn nữa
    C Code:
    1. if(n == 2 || n == 3)
    2. {
    3.     return true;
    4. }
    5.  
    6. if( n == 1 || n == 2 || n % 2 == 0 || n % 3 == 0)
    7. {
    8.     return false;
    9. }
    Ở trên nếu n==2 thì True, vậy phía dưới có cần phải || n==2 ... return false?
    Còn hệ số 6 (giống một topic mà bác huynguyen có nói qua qua, hoặc tích của các số nguyên tố), vậy có thể dùng hệ số nào khác không?

    Còn chỗ này sai nữa :
    C Code:
    1. while(i <= floor(sqrt(n)))  
    2. {
    3.     if(n % i == 0 )
    4.     {
    5.         return false;
    6.         break;
    7.     }
    8.     else
    9.     {
    10.         i = i + j ;
    11.         j = 6 - j ;
    12.         return true;
    13.     }
    14. }
    Cần phải cho return true; về cuối while loop. Như vậy mới đúng.(không tin? bạn thử nhập vô số 123 rồi run xem).
    Đã được chỉnh sửa lần cuối bởi NT_OnlyLove : 23-11-2007 lúc 11:07 PM. Lý do: [Sau khi chạy thử, phát hiện một chỗ nữa chưa ổn]
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  7. #7
    Ngày gia nhập
    10 2007
    Nơi ở
    /root
    Bài viết
    318

    123 chia hết cho 3 : Không là nguyên tố / Test :cout<<CheckNguyenTo(123) :kq = 0(false) ???
    Còn hệ số 6 :không thể có hệ số nào khác , vậy thôi.

    Chậc, test một lúc thấy ra lắm lỗi quá , bài này tớ làm cách đây lâu rồi , từ hồi bắt đầu học C++, xin được sửa lại:

    C Code:
    1. bool CheckNguyenTo(int n)
    2. {
    3.     if(n == 2 || n == 3)
    4.     {
    5.         return true;
    6.     }
    7.     if( n == 0 || n == 1 || n % 2 == 0 || n % 3 == 0)
    8.     {
    9.         return false;
    10.     }
    11.     if( n < 25 )
    12.     {
    13.         return true;
    14.     }
    15.     int i = 5 ;
    16.     int j = 2 ;
    17.     while(i <= floor(sqrt(n)))
    18.     {
    19.         if(n % i == 0 )
    20.         {
    21.             return false;
    22.         }
    23.         else
    24.         {
    25.             i = i + j ;
    26.             j = 6 - j ;
    27.            
    28.         }
    29.     }
    30.     return true;  
    31. }

    Như vậy đã được chưa nhỉ ?:-??

    Giải thích thêm về hệ số 6 :Nếu n là một sô nguyên tố́ lớn hơn 5 thì phần dư của phép chia cho 6 chỉ có thể là 1 hoặc 5.
    Đã được chỉnh sửa lần cuối bởi iamvtn : 24-11-2007 lúc 12:04 AM.

  8. #8
    Ngày gia nhập
    11 2007
    Bài viết
    153

    Cám ơn các bạn rất nhiều giờ thì mình hiểu rồi!

  9. #9
    Ngày gia nhập
    06 2007
    Nơi ở
    một nơi xa xăm...
    Bài viết
    127

    Cả 2 cách của DR và zkday đều cho kết quả.Nhưng cách của DR sẽ chạy nhanh hơn vì phải kiểm tra ít hơn

  10. #10
    Ngày gia nhập
    10 2007
    Nơi ở
    /root
    Bài viết
    318

    Trích dẫn Nguyên bản được gửi bởi Alviss Xem bài viết
    Cả 2 cách của DR và zkday đều cho kết quả.Nhưng cách của DR sẽ chạy nhanh hơn vì phải kiểm tra ít hơn
    Cách của DR không chạy nhanh hơn , nó không phải là tối ưu .

Các đề tài tương tự

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. thuật toán số nguyên tố????
    Gửi bởi anhtbok trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 30-03-2012, 10:33 AM
  3. Tìm và in ra các số nguyên tố thỏa mãn đề bài bằng C, thuật toán của mình sai ở đâu?
    Gửi bởi piavg trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 8
    Bài viết cuối: 16-11-2011, 04:03 PM
  4. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM
  5. Hàng đợi | Thuật toán in đảo số nguyên n
    Gửi bởi hoangchauhamy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 18-05-2009, 08:37 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn