Lưu trữ hiệu quả các số nguyên tố

Question

Đối với thư viện, tôi cần lưu trữ số nguyên tố đầu tiên lên đến giới hạn L. Bộ sưu tập này phải có thời gian tra cứu O (1) (để kiểm tra xem số có là số nguyên tố hay không) và nó phải dễ dàng, được đưa ra một số, để tìm số nguyên tố tiếp theo (giả sử nó nhỏ hơn L).

Cho rằng L là cố định, một sàng Eratostene để tạo danh sách là tốt. Ngay bây giờ, tôi sử dụng một mảng boolean đóng gói để lưu trữ danh sách, trong đó chỉ chứa các mục cho các số lẻ giữa 3 và L (bao gồm). Điều này có (L-2)/2 bit bộ nhớ. Tôi muốn có thể tăng L mà không cần sử dụng nhiều bộ nhớ hơn.

Có cấu trúc dữ liệu nào sử dụng ít bộ nhớ hơn với các thuộc tính tương tự không? Hoặc với ít nhất là thời gian tra cứu liên tục? (Số lẻ sau đó có thể được liệt kê cho đến khi chúng tôi có được một số nguyên tố)

(ngôn ngữ tôi đã viết trong này là Factor nhưng câu hỏi này sẽ là như nhau trong bất kỳ ngôn ngữ mà đã tích hợp sẵn hoặc dễ dàng lập trình mảng chút đóng gói)

Answer 1

Bạn có thể kiểm tra rõ ràng các số nguyên tố khác để xóa dự phòng.

Hiện tại, bạn chỉ thực hiện việc này cho hai lần, bằng cách kiểm tra tính chia nhỏ theo hai cách rõ ràng và sau đó chỉ lưu trữ số lẻ nếu chúng là số nguyên tố.

Đối với 2 và 3 bạn nhận được số dư từ 0 đến 5, trong đó chỉ 1 và 5 không chia hết cho hai hoặc ba và có thể dẫn đến số nguyên tố, do đó bạn giảm xuống 1/3.

Đối với 2, 3 và 5, bạn nhận được 8 con số trong số 30, rất tốt để lưu trữ trong một byte.

Điều này được giải thích chi tiết hơn here.

Answer 2

Nếu bạn có thể tìm ra số nào là Mersenne hoặc các số nguyên tố được đại diện dễ dàng khác, bạn có thể lưu một vài bit bằng cách sử dụng biểu diễn đó với cờ cho các số có thể áp dụng.

Ngoài ra, cách lưu trữ các con số là sự khác biệt so với số trước đó? Sau đó, kích thước không nên tăng khá nhanh (nhưng tra cứu sẽ chậm). Kết hợp với cách tiếp cận trên, bạn có thể lưu trữ số nguyên tố Mersenne và sự khác biệt so với nguyên tố Mersenne cuối cùng.

Answer 3

Với bộ nhớ đó quá rẻ, tôi không nghĩ bạn có thể làm tốt hơn nhiều so với phối cảnh tốc độ so với sơ đồ hiện có của bạn.

Nếu có một giải pháp tốt hơn, sau đó tôi sẽ giả định nó muốn tận dụng lợi thế của Prime Number Theorem cho thấy rằng như L lớn hơn, giới hạn của

π (L)/(L/ln (L)) phương pháp tiếp cận 1.

Có lẽ giải pháp tốt hơn sẽ có giải pháp đóng gói thích ứng trong cấu trúc dữ liệu có dạng như skip list.

Answer 4

Có thể cấu trúc dữ liệu trie chỉ chứa số nguyên tố bạn đang tìm kiếm. Thay vì sử dụng ký tự làm chỉ mục, bạn có thể sử dụng các số nguyên. Việc triển khai thực hiện điều này là Judy-Array s. Chúng tôi không đáp ứng yêu cầu O (1) của bạn, chúng cực kỳ hiệu quả về bộ nhớ cho các khóa tương tự (như hầu hết các phần của số) và khá nhanh để tìm kiếm một phím O (m) (m =) chiều dài) tối đa.

Nếu bạn tìm kiếm một số nguyên tố trong cây được tạo trước, bạn có thể đi bộ cây cho đến khi bạn tìm thấy cây đó hoặc bạn đã ở nút bên cạnh tiền tố trước và sau.

Answer 5

Hiện tại bạn đang coi 2 là trường hợp đặc biệt và sau đó có một mảng trong đó mọi số lẻ được ánh xạ tới một phần tử trong mảng (với một số số lẻ là số nguyên tố). Bạn có thể cải thiện điều này bằng cách xử lý 2 và 3 khi các trường hợp đặc biệt nhận ra rằng phần còn lại của số nguyên tố ở dạng 6n + 1 hoặc 6n-1 (nghĩa là cho tất cả số nguyên tố p trong đó p> 3, p mod 6 = 1 hoặc 5). Điều này có thể được tổng quát hơn nữa - xem Wikipedia. Đối với tất cả số nguyên tố p> 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 hoặc 29. Bạn có thể tiếp tục với điều này và giảm bộ nhớ cần thiết với chi phí thời gian xử lý (mặc dù nó vẫn sẽ là O (1), chỉ là O (1) chậm hơn.

Answer 6

Làm thế nào về một số loại bảng băm?

Bạn sẽ cần một hàm băm rất tốt (cái gì đó như n mod p, nơi p không phải là một bội số của bất kỳ q số nguyên tố thấp nhất - chọn q đủ cao để giảm thiểu số lượng va chạm).

Answer 7

Một giải pháp thay thế cho bitmap và bánh xe được đóng gói - nhưng hiệu quả không kém trong các ngữ cảnh nhất định - đang lưu trữ sự khác biệt giữa các số nguyên tố liên tiếp. Nếu bạn bỏ qua số 2 như bình thường thì tất cả các khác biệt đều là. Lưu trữ sự khác biệt/2 bạn có thể nhận được lên đến 2^40 khu vực (ngay trước 1999066711391) bằng cách sử dụng các biến cỡ byte.

Các số nguyên tố lên 2^32 chỉ yêu cầu 194 MByte, so với 256 MByte cho bitmap được đóng gói chỉ có tỷ lệ cược. Lặp lại các số nguyên tố được lưu trữ bằng đồng bằng nhanh hơn nhiều so với lưu trữ được bánh xe, bao gồm bánh xe modulo-2 được gọi là bitmap chỉ có tỷ lệ cược.

Đối với phạm vi từ 1999066711391 trở đi, cần có kích thước ô lớn hơn hoặc dung lượng có độ dài thay đổi. Cái sau có thể vô cùng hiệu quả ngay cả khi các lược đồ rất đơn giản được sử dụng (ví dụ: tiếp tục thêm cho đến khi một byte < 255 được thêm vào, như nén theo kiểu LZ4), do tần số cực thấp của khoảng trống dài hơn 510/2.

Vì mục đích hiệu quả, tốt nhất nên chia phạm vi thành các phần (trang) và quản lý kiểu B-Tree.

Sự khác biệt giữa mã hóa (Huffmann hoặc mã số học) cắt giảm yêu cầu lưu trữ vĩnh viễn xuống ít hơn một nửa, gần với lý thuyết tối ưu và tốt hơn danh sách hoặc bánh xe được nén bằng các trình đóng gói sẵn có tốt nhất.

Nếu dữ liệu được lưu trữ không nén thì nó vẫn nhỏ gọn hơn nhiều so với tệp nhị phân hoặc số văn bản, theo thứ tự độ lớn hoặc nhiều hơn. Với chỉ số kiểu B-Tree tại chỗ, thật dễ dàng để chỉ đơn giản là ánh xạ các phần vào bộ nhớ khi cần và lặp lại chúng với tốc độ nhanh.

Answer 8

Kiểm tra hướng dẫn Topcoder về số nguyên tố: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders

Answer 9

Làm thế nào về một cây Interval? http://www.geeksforgeeks.org/interval-tree/

Nó có thể không phải là O (1) nhưng nó thực sự rất nhanh. Giống như có thể O (log (p (n))) trong đó p (n) là số lượng số nguyên tố cho đến số n. Bằng cách này, bạn sẽ nhớ bộ nhớ bạn cần sẽ chỉ cân bằng với số lượng số nguyên tố, giảm đáng kể chi phí bộ nhớ.Ví dụ giả sử bạn tìm số nguyên tố p1 và sau đó là p2, Chèn khoảng thời gian (p1, p2), v.v. và khi bạn chạy tìm kiếm bất kỳ số nào trong phạm vi đó, nó sẽ trả về khoảng thời gian này và bạn có thể trả lại p2, đó sẽ là câu trả lời trong trường hợp của bạn.