Announcement

Collapse
No announcement yet.

Hỏi về vấn đề tối ưu tìm số nguyên số!

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • [C++] Hỏi về vấn đề tối ưu tìm số nguyên số!

    Chào mọi người!
    Em giải đề tìm các số nguyên số thứ K (K<=50,000,000) bên dưới theo phương pháp sàn tới căn bậc 2, nhưng thời gian chạy tới 20s trong khi giới hạn của đề chỉ 1s!
    Mong mọi người chỉ dẫn! Em cảm ơn!

    Link đề: http://www.spoj.com/problems/KPRIMES2/

    Ảnh file cpp + thời gian chạy: http://i345.photobucket.com/albums/p...psrzdzd6kv.png

    Em không tải file .cpp lên được nên gửi văn bản code luôn:

    #include <iostream>
    #include<math.h>
    #include <vector>

    #define S 982451656//1000000000
    #define d 8
    using namespace std;

    long c=0,i,j ,e=5,f;
    long m[50000000], a[100000];
    bool b[S]={false};
    //vector<long> m;
    int main()
    {
    vector<long> m;
    //cin >> d;
    f=sqrt(S);
    for (i=2; i<f; i++)
    if (!b[i]) {
    m.push_back(i);
    for (j=i*i; j<S ; j+=i)
    b[j] = true;
    }
    for (i=f; i<S; i++)
    if (!b[i]) m.push_back(i);

    for (int x=0; x<d; x++){ // TỰ SINH 8 SO GIONG BO TEST
    a[x]=e;
    e=e*10;
    cout << m[a[x]-1] << endl;
    }

    return 0;
    }

  • #2
    https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes

    Có sàng Eratosthenes từ thời cổ chí kim người ta nghiên cứu và có thể áp dụng được cho bài này. Cũng khá thú dị :3
    Nguyễn Ôn Ngọc Bảo
    [Khoa học máy tính K12 - Đại học Công nghệ thông tin]
    [Marketing Content Internship - VNG Recruitment]

    Comment


    • #3
      Tui làm cách sàng đó á! Mà tại số lớn nên mất tới 20s...

      Comment


      • #4
        Em sửa lại code cho dễ nhìn đi. Forum có chức năng format code cơ mà. Forum cũng có chức năng up mình mà, hình của em die rồi kìa.

        Comment


        • #5
          Dạ thầy!

          aaaaaaaaaaaaaaaaaaa.png

          Code:
          #include <iostream>
          #include<math.h>
          #include <vector>
          
          #define S 982451656//1000000000
          #define      d 8
          
          using namespace std;
          
          long c=0,i,j ,e=5,f;
          long m[50000000], a[100000];
          bool b[S]={false};
          
          int main()
          {
             vector<long> m;
             f=sqrt(S);
             
             for (i=2; i<f; i++)
                  if (!b[i]) {
                      m.push_back(i);
                      for (j=i*i; j<S ; j+=i)
                          b[j] = true;
                  }
              for (i=f; i<S; i++)
                  if (!b[i]) m.push_back(i);
          
              for (int x=0; x<d; x++){   // TỰ SINH 8 SO GIONG BO TEST
                  a[x]=e;
                  e=e*10;
                  cout << m[a[x]-1] << endl;
              }
              return 0;
          }
          Attached Files
          17520330
          Hồ Trần Thiện Đạt
          Last edited by 17520330; 10-10-2017, 22:35.

          Comment


          • #6
            Originally posted by 17520330 View Post
            Dạ thầy!

            [ATTACH=CONFIG]22857[/ATTACH]

            Code:
            #include <iostream>
            #include<math.h>
            #include <vector>
            
            #define S 982451656//1000000000
            #define      d 8
            
            using namespace std;
            
            long c=0,i,j ,e=5,f;
            long m[50000000], a[100000];
            bool b[S]={false};
            
            int main()
            {
               vector<long> m;
               f=sqrt(S);
               
               for (i=2; i<f; i++)
                    if (!b[i]) {
                        m.push_back(i);
                        for (j=i*i; j<S ; j+=i)
                            b[j] = true;
                    }
                for (i=f; i<S; i++)
                    if (!b[i]) m.push_back(i);
            
                for (int x=0; x<d; x++){   // TỰ SINH 8 SO GIONG BO TEST
                    a[x]=e;
                    e=e*10;
                    cout << m[a[x]-1] << endl;
                }
                return 0;
            }
            Mình và thằng bạn từng tranh cãi về cái này :v cách thằng bạn mình thì giống cách của bạn. Còn cách mình là thay vì lấy n chia cho các số trong khoảng từ 2 -> căn n thì mình lấy n chia cho các số nguyên tố nằm trong khoảng từ 2 -> căn n
            Vì là chém võ mồm nên đến giờ không biết cách nào nhanh hơn :v

            Comment

            LHQC

            Collapse
            Working...
            X