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

[17520330]

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;
}

[17520273]

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

[17520330]

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

[truonganpn]

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.

[17520330]

Dạ thầy!

aaaaaaaaaaaaaaaaaaa.png

#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;
}

[15520359]

Dạ thầy!

[ATTACH=CONFIG]22857[/ATTACH]

#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