Tìm n số nguyên tố lớn hơn một giá trị cho trước

[08520604]

Tiện thể nói về Prime ,Trước có bài tìm số nguyên tố bị chặn trên ( cho trước một số n ,tìm các số nguyên tố trong khoảng 1 --> n).
Giờ ta đổi đề 1 tí , cho trước maxBound và n , tìm n số nguyên tố kế tiếp lớn hơn maxBound ?

Chúc ngủ ngon

p/s : Giả sử là trong khả năng tính toán của máy tính đi , hình như là 200.000 gì đó ,rồi điều kiện là Memory < 16MB , t < 2000ms gì gì đó )

[09520019]

Tiện thể nói về Prime ,Trước có bài tìm số nguyên tố bị chặn trên ( cho trước một số n ,tìm các số nguyên tố trong khoảng 1 --> n).
Giờ ta đổi đề 1 tí , cho trước maxBound và n , tìm n số nguyên tố kế tiếp lớn hơn maxBound ?

Chúc ngủ ngon

anh Toàn đang nói tới hàm nextPrime ? Em xem PARI (1 chương trình trâu chó về toán học) thì hàm nextprime nó sử dụng rabbinMiller và rất ảo:
for (i = maxBound + 1;rabbinMiller(i) == 0;++i);

[08520604]

anh Toàn đang nói tới hàm nextPrime ? Em xem PARI (1 chương trình trâu chó về toán học) thì hàm nextprime nó sử dụng rabbinMiller và rất ảo:
for (i = maxBound + 1;rabbinMiller(i) == 0;++i);

Chà ,nếu công thức xác suất được tối giản thành cái ++i này thì có lẽ mình mới thêm cái điều kiện vào là dư rồi, có lẽ nên sửa lại là "Do not care about performance or memory limitation , just make it work " .
Có bạn nào có ý kiến nào khác không ? giúp ở đây với

[07520004]

Tiện thể nói về Prime ,Trước có bài tìm số nguyên tố bị chặn trên ( cho trước một số n ,tìm các số nguyên tố trong khoảng 1 --> n).
Giờ ta đổi đề 1 tí , cho trước maxBound và n , tìm n số nguyên tố kế tiếp lớn hơn maxBound ?

Chúc ngủ ngon

p/s : Giả sử là trong khả năng tính toán của máy tính đi , hình như là 200.000 gì đó ,rồi điều kiện là Memory < 16MB , t < 2000ms gì gì đó )

anh Toàn đang nói tới hàm nextPrime ? Em xem PARI (1 chương trình trâu chó về toán học) thì hàm nextprime nó sử dụng rabbinMiller và rất ảo:
for (i = maxBound + 1;rabbinMiller(i) == 0;++i);

Ra topic khác đi 2 chú. Em nó nói một bài siêu cơ bản mà đàn anh bay vô quất xuất chiêu tung chưởng mịt mù lên ớn quá. Bài này cũng hay nè, để nguyên một topic mới thì hợp hơn. Với khả năng google và vọc phá của sinh viên thì có khả năng nó sẽ biến tướng thành một vấn đề quá khó so với chương trình đại học

[09520019]

Chà ,nếu công thức xác suất được tối giản thành cái ++i này thì có lẽ mình mới thêm cái điều kiện vào là dư rồi, có lẽ nên sửa lại là "Do not care about performance or memory limitation , just make it work " .
Có bạn nào có ý kiến nào khác không ? giúp ở đây với

Anh làm ơn post đề full đi anh mới sửa đề kìa. 200k gì ? 200k chữ số hay maxBound < 200.000 ?

PS: em đã đọc kỹ lại đề và tình hình là em đọc nhầm "n số nguyên tố kế tiếp lớn hơn maxBound" thành số nguyên tố kế tiếp lớn hơn maxBound, Ngoài ra giới hạn là gì ?

[09520019]

giữa việc tính sqrt(n) một lần với việc tính sqrt(n) lần số i*i chưa chắc cái nào nhanh hơn nha. Ở đây mình chỉ cần phần nguyên của căn bậc hai nên chắc là có cách tính nhanh, nhưng mà thôi cũng không cải thiện được bao nhiêu

sqrt(n) đã là 1 lệnh hợp ngữ rồi nên tốc độ nó nhanh gần bằng việc cộng trừ nhân chia hay xoay bit, nhưng xử lý số thực vẫn chậm hơn xử lý số nguyên 1 tẹo phải ko anh ? Nhanh hơn 1 tí cũng chả sao, nhưng quan trọng là em code số thực thấy nó ảo lắm vì cái vụ 3 = 2.999999999999997 nên em thường hay code i * i <= n hơn là i <= sqrt(n) là ở chỗ đó

Với một hàm đơn giản như isprime thì compiler sẽ tự động inline nó, hầu hết các compile bây giờ đều vậy nên chúng ta cũng không cần quan tâm quá tới vụ này.

Cái này em đang quan tâm, vì em đọc hướng dẫn chỉ thị compile (compile parameter) có đoạn optimization -O1, -O2, -O3 và -Os của GNU C/C++, có đoạn nói là không optimization và O1 thì tất cả các hàm inline xem như gọi hàm, chỉ khi -O2 và -O3 trở lên mới compile hẳn đoạn inline. Em không rành về GNU nên nếu đc anh An xem giúp nhé. Còn Visual Studio theo quảng cáo thì sẽ tự động làm vụ inline luôn

[08520604]

Anh làm ơn post đề full đi anh mới sửa đề kìa. 200k gì ? 200k chữ số hay maxBound < 200.000 ?

Uh để "biểu diễn " đề :

Viết thủ tục tìm kiếm danh sách n số nguyên tố (Lp) lớn hơn một số cho trước.
Trong đó Lp được biểu diên như sau : Lp = [p1, p2 ,....., pi] sao cho pi <= 200.000.

p/s :Vì sao là 200.000 ? Vì mình lấy theo kết quả của
http://forum.uit.edu.vn/threads/2177...uyen-to-tu-N-M mà theo đó ,thuật toán tìm kiếm các số nguyên tố theo giới hạn trên cho trước có thể tìm ra bằng thuật toán sàn Eratos chạy còn ra.

[09520019]

Uh để "biểu diễn " đề :

Viết thủ tục tìm kiếm danh sách n số nguyên tố (Lp) lớn hơn một số cho trước.
Trong đó Lp được biểu diên như sau : Lp = [p1, p2 ,....., pi] sao cho pi <= 200.000.

p/s :Vì sao là 200.000 ? Vì mình lấy theo kết quả của
http://forum.uit.edu.vn/threads/2177...uyen-to-tu-N-M mà theo đó ,thuật toán tìm kiếm các số nguyên tố theo giới hạn trên cho trước có thể tìm ra bằng thuật toán sàn Eratos chạy còn ra.

gọi số cho trước đó là x
Nếu maxBound đó < 200k thì ko cần sàn cũng được anh, cứ chạy hàm prime như em thời gian là O(n căn n),
dạng như
for (i = x + 1;(i < 200k) && (listprime.size() < n);++i)
if (isPrime(i)) listprime.push_back(i);

Mỗi lần isPrime(i) tốn O(căn n), chạy vòng for tốn O(n), tóm lại là O(n căn n), n = 200k thì time limit 2s là nổi.

[08520604]

Rồi, thế là ( n căn n) ,chúc các bạn ngủ ngon.

p/s : Cảm ơn Mod/Admin đã dạo qua thăm hỏi .