Thuật toán song song để tạo số nguyên tố (có thể sử dụng bản đồ của Hadoop giảm)

Question

Tạo số nguyên tố là vấn đề đồ chơi mà tôi thường cố gắng, đặc biệt khi thử nghiệm với ngôn ngữ lập trình, nền tảng hoặc kiểu mới.

Tôi đã nghĩ đến việc cố gắng viết một thuật toán Tạo số nguyên tố hoặc Thuật toán kiểm tra số nguyên tố bằng cách sử dụng Hadoop (Map Reduce).

Tôi nghĩ tôi muốn đăng câu hỏi này để nhận mẹo, tham chiếu, thuật toán, phương pháp tiếp cận.

Mặc dù sự quan tâm chính của tôi là một bản đồ Giảm thuật toán dựa Tôi sẽ không phiền nhìn vào mô hình lập trình Hadoop mới hoặc ví dụ xem xét sử dụng PiCloud

tôi có vẻ như một số câu hỏi thú vị ở đây trên Thủ Số Generation: here, here và here, nhưng không có gì liên quan đến cách tiếp cận song song bắt gặp ánh mắt của tôi.

Xin cảm ơn trước.

Answer 1

Đây là an algorithm được xây dựng trên bản đồ và giảm (folding). Nó thể hiện sieve of Eratosthenes

        P = {3,5,7, ...} \ U {{p , p + 2p, p + 4p, ...} | p trong P}

cho số nguyên tố lẻ (nghĩa là không có 2). Gấp được vô hạn định sâu sắc về bên phải, như thế này:

trong đó mỗi số nguyên tố đánh dấu một dòng bội lẻ của nguyên tố đó, ví dụ cho : 49, 49 + 14, 49 + 28, ..., tất cả được kết hợp để có được tất cả các hợp số, và sau đó số nguyên tố được tìm thấyvào những khoảng trống giữa hợp số. Đó là trong Haskell, do đó, thời gian được xử lý hoàn toàn bởi cơ chế đánh giá lười biếng _{(và điều chỉnh thuật toán trong đó mỗi nút so sánh luôn cho phép thông qua số đầu tiên từ bên trái mà không yêu cầu số từ bên phải, bởi vì nó là đảm bảo lớn hơn)}.

Tỷ lệ có thể được sử dụng thay cho số nguyên tố lẻ làm hạt cho thế hệ bội số, để đơn giản hóa mọi thứ (với ý nghĩa hiệu suất rõ ràng).

Công việc có thể được chia thành các phân đoạn giữa các ô số nguyên tố liên tiếp.Haskell đang sau, nhưng chúng ta có thể coi đó là một giả thực thi quá _{(nơi : là danh sách nút constructor lười biếng, một cuộc gọi chức năng f(x) được viết f x, và dấu ngoặc đơn được sử dụng để chỉ nhóm)}:

primes() = 2 : ([3,5..] `minus` unionAll [[p*p, p*p+2*p..] | p <- prs]) 
    where 
    prs = 3 : ([5,7..] `minus` unionAll [[p*p, p*p+2*p..] | p <- prs]) 
    unionAll ((x:xs):t) = x : union xs (unionAll (pairs t)) 
    pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t 

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union xs (y:ys) 
    EQ -> x : union xs ys 
    GT -> y : union (x:xs) ys 

minus (x:xs) (y:ys) = case compare x y of 
    LT -> x : minus xs (y:ys) 
    EQ ->  minus xs ys 
    GT ->  minus (x:xs) ys 

Cuộc thảo luận là here. Phức tạp hơn, lập lịch lazer là here. Đồng thời this SO answer hiển thị bản dịch gần đúng của mã Haskell (liên quan) về máy phát điện.