Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Thuật giải đếm số nguyên tố

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

    Mặc định Thuật giải đếm số nguyên tố

    Em muốn đến các số nguyên tố từ 1 đến 100.000.000
    Thuật giải của em như sau :
    Code:
                int so=1;
                bool co=true;
                for(int i = 2 ; i<100000000 ; i++)
                {
                    for(int j=2;j<Math.Sqrt(i)+1;j++)
                    {
                        if (i % j == 0)
                        {
                            co = false;
                            break;
                        }
                        else co = true;
                    }
                    if (co)
                    {
                        so++;
                    }
                }
    Tuy nhiên với thuật giải này nó chạy quá lâu .Nghe nói trong C# còn 1 thuật giải khác để đếm (hoặc in ra) số nguyên tố hiệu quả hơn nhiều lần ! Ai biết có thể cho em tham khảo được không ạ ?

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    Nếu chạy với số lượng lớn như vậy thì nên code multi thread . Có thể refine đoạn code trên giúp chạy nhanh hơn "tí xíu" còn thuật toán hiệu quả hơn thì ko biết có hay ko .
    Keep moving forward!

    ... Retired ...

  3. #3
    Ngày gia nhập
    03 2007
    Bài viết
    179

    bạn nên thêm hay dòng code sau ở phía trên khi tìm số nguyên tố(không phải tìm 1 dãy như trên mà tìm một số bất kì
    Code:
    if(n<2) return 0;//false
    	if(n==2) return 1;//true

  4. #4
    Ngày gia nhập
    06 2007
    Nơi ở
    HCM
    Bài viết
    365

    Trích dẫn Nguyên bản được gửi bởi LPS86 Xem bài viết
    Em muốn đến các số nguyên tố từ 1 đến 100.000.000
    Thuật giải của em như sau :
    Code:
                int so=1;
                bool co=true;
                for(int i = 2 ; i<100000000 ; i++)
                {
                    for(int j=2;j<Math.Sqrt(i)+1;j++)
                    {
                        if (i % j == 0)
                        {
                            co = false;
                            break;
                        }
                        else co = true;
                    }
                    if (co)
                    {
                        so++;
                    }
                }
    Tuy nhiên với thuật giải này nó chạy quá lâu .Nghe nói trong C# còn 1 thuật giải khác để đếm (hoặc in ra) số nguyên tố hiệu quả hơn nhiều lần ! Ai biết có thể cho em tham khảo được không ạ ?
    Nếu hiểu rõ hơn chút bạn sẽ giảm được 70% vòng lặp, đương nhiên tăng tốc độ lên 300%
    + Các số chẵn > 2 không thể là các số nguyên tố( để bước lặp ++ 2, bỏ qua tất cả các số chẵn )
    + Các số chia hết cho 3,5,7 không thể là số nguyên tô( ngoại trừ 3,5,7)

  5. #5
    Ngày gia nhập
    12 2007
    Bài viết
    31

    Trích dẫn Nguyên bản được gửi bởi phamtiensinh Xem bài viết
    Nếu hiểu rõ hơn chút bạn sẽ giảm được 70% vòng lặp, đương nhiên tăng tốc độ lên 300%
    + Các số chẵn > 2 không thể là các số nguyên tố( để bước lặp ++ 2, bỏ qua tất cả các số chẵn )
    + Các số chia hết cho 3,5,7 không thể là số nguyên tô( ngoại trừ 3,5,7)
    Hix code trên là em viết đơn giản ra để mà mọi người hiểu rõ về thuật toán của em thôi *_*Chứ trong bài dĩ nhiên là em phải có chỉnh sửa cho nhanh hơn chút xíu .Tuy nhiên vẫn quá chậm .Xử lí đến 100tr mất 10ph lận ,trong khi đề ra là 1 ph *_*
    Theo Training thì cho vào 1 cái mảng .Sau dó chia các số của mảng cho số ở vị trí thứ nhất (bắt đầu từ số 2). Các số chia hết cho số bé nhất thì bị loại ra khỏi mảng *_* Tức là sau khi làm 100tr phép chia ta còn lại 50 tr số lẻ .Tiếp đó chia cho vị trí thứ 2 của mảng là số 3.Tức là làm 50tr phép tính nữa .Ta sẽ còn lại 33,33 tr số .Tiếp tục chia cho vị trí thứ 3 là số 5 (vì số 4 đã bị loại khỏi mảng do chia hết cho 2).Tức là làm tiếp 33,33 tr phép tính nữa ta sẽ còn 23,33tr số..... Cứ như vậy cho đến khi số tại index > 10.000(căn 2 của 100tr) thì ngưng và in mảng ra *_*
    Lí thuyết là thế và ông thầy cũng biểu diễn ,nó chạy có chưa đến 10s *_*Nhưng em không biết biến nó thành thuật toán thế nào ! Mong các bác giúp đỡ

    Về chuyện bước lặp +2 như bạn nói thì thực ra cũng chỉ bớt được 3*50tr = 150tr phép tính(mỗi số chẵn cần 3 phép tính là loại được rồi).Chia hết cho 3,5,7 cũng không mất nhiều thơi gian đâu *_* Cái làm mất nhiều thời gian nhất là các số nguyên tố kìa .
    Đã được chỉnh sửa lần cuối bởi LPS86 : 28-12-2007 lúc 07:00 AM. Lý do: Bổ sung

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

  1. Cần giải thích chi tiết thuật toán tìm số nguyên tố?
    Gửi bởi dangngocgiabao trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 13-09-2013, 06:10 PM
  2. 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
  3. Trả lời: 11
    Bài viết cuối: 17-06-2011, 12:25 AM
  4. Lập trình C++ Giải thuật nhân 2 số nguyên lớn trên C++?
    Gửi bởi kaka_nsk_91 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 03-04-2010, 10:29 PM
  5. Cho hỏi kĩ hơn về thuật giải bài tìm số nguyên tố
    Gửi bởi chocolate1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 19
    Bài viết cuối: 13-02-2008, 03:43 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