प्राइम नंबर जेनरेट करने के लिए समांतर एल्गोरिदम (संभवतः हडोप के मानचित्र का उपयोग करने के लिए)

Question

जेनरेटिंग प्राइम नंबर एक खिलौना समस्या है जिसे मैं अक्सर समय-समय पर प्रयास करता हूं, खासकर जब एक नई प्रोग्रामिंग भाषा, मंच या शैली के साथ प्रयोग करते हैं।

मैं हाडोप (मानचित्र कम करने) का उपयोग करके प्राइम नंबर जेनरेशन एल्गोरिदम या प्राइम नंबर टेस्ट एल्गोरिदम लिखने का प्रयास कर रहा था।

मैंने सोचा कि मैं इस सवाल को सुझाव, संदर्भ, एल्गोरिदम, दृष्टिकोण प्राप्त करने के लिए पोस्ट करूंगा।

हालांकि मेरी प्राथमिक हित एक मानचित्र में कमी आधारित एल्गोरिथ्म मैं नए Hadoop प्रोग्रामिंग मॉडल को देखकर कोई फ़र्क नहीं पड़ेगा या उदाहरण के लिए का उपयोग कर PiCloud

मैं प्रधान संख्या पीढ़ी पर यहाँ कुछ दिलचस्प सवाल लगता है पर देख रहा है: here, here और here, लेकिन समांतर दृष्टिकोण से संबंधित कुछ भी मेरी आंख को पकड़ा नहीं।

अग्रिम धन्यवाद।

Answer 1

यहां an algorithm है जो मानचित्रण और घटाने पर बनाया गया है (folding)। यह व्यक्त करता sieve of Eratosthenes

        पी = {3,5,7, ...} \ यू {{पी , पी + 2p, पी + 4 पी, ...} | पी}

अजीब अभाज्य संख्या के लिए

हैं (यानी 2 के बिना) में पी। तह अनिश्चित काल के लिए सही करने के लिए मजबूत बनाने की है, इस तरह:

जहां प्रत्येक अभाज्य संख्या है कि प्रधानमंत्री, उदा की विषम गुणकों की एक धारा के निशान के लिए: 49, 49 + 14, 49 + 28, ..., सभी सभी संयुक्त संख्या प्राप्त करने के लिए बनाए गए हैं, जो है, और फिर अभाज्य संख्या अंतराल में पाए जाते हैं संयुक्त संख्या के बीच। यह हास्केल में है, इसलिए समय को आलसी मूल्यांकन तंत्र _{(और एल्गोरिदमिक समायोजन) द्वारा समेकित रूप से देखभाल की जाती है, जहां प्रत्येक तुलना नोड हमेशा को दाएं से दाएं से नंबर की मांग किए बिना बाईं ओर नंबर देता है, क्योंकि यह है वैसे भी बड़ा होने की गारंटी)}।

बाधाएं चीजों को सरल बनाने के लिए विषम प्राइम्स के बजाय विषम प्राइम्स के बजाय बाधाओं का उपयोग किया जा सकता है (स्पष्ट प्रदर्शन प्रभाव के साथ)।

काम स्वाभाविक रूप से लगातार प्राइम के वर्गों के बीच खंडों में विभाजित किया जा सकता है।हास्केल कोड इस प्रकार है, लेकिन हम एक निष्पादन योग्य स्यूडोकोड के रूप में यह मानते हैं कर सकते हैं भी _{(जहां : एक सूची नोड आलसी निर्माता, एक समारोह कॉल f(x)f x लिखा है, और कोष्ठक केवल समूहीकरण के लिए उपयोग किया जाता है)}:

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 

एक चर्चा here है। अधिक परिष्कृत, आलसी शेड्यूलिंग here है। इसके अलावा this SO answer जनरेटर के संदर्भ में (संबंधित) हास्केल कोड का अनुमानित अनुवाद दिखाता है।