हास्केल

Question

में divisors की एक सूची बनाना मैं eulerproject में समस्या 21 कर रहा हूँ। एक भाग को किसी संख्या के उचित divisors की सूची खोजने की आवश्यकता है। यानी जहां n शेष है और कुछ संख्या n से कम है। इसलिए मैंने यह हास्केल बनाया, लेकिन जीएचसीआई मुझ पर नाराज हो गया।

divisors n =[ n | n <- [1..(n-1)], n `rem` [1..(n-1)] ==0 ] 

समस्या यह है कि मैं नहीं जानता कि कैसे बनाने के लिए है:

n `rem` [1..(n-1)] 

इतना है कि यह केवल संख्या n कि n में समान रूप से विभाजित की तुलना में कम देता है।

Answer 1

आपको बस एक अलग चर की आवश्यकता है।

Prelude> let divisors n = [x | x <- [1..(n-1)], n `rem` x == 0] 
Prelude> divisors 20 
[1,2,4,5,10] 
Prelude> divisors 30 
[1,2,3,5,6,10,15] 

अब, अगर आप इसे थोड़ा और अधिक कुशल बनाना चाहते थे, हम पहले से ही जानते हैं कि एक भाजक n के आधे से अधिक नहीं होगा, और हम जानते हैं 1 सब कुछ का एक भाजक है।

Prelude> let divisors n = 1 : filter ((==0) . rem n) [2 .. n `div` 2] 
Prelude> divisors 20 
[1,2,4,5,10] 
Prelude> divisors 30 
[1,2,3,5,6,10,15] 
Prelude> divisors 31 
[1] 

Answer 2

हैं divisors के सूची के क्रम महत्वपूर्ण नहीं है, तो आप इस काफी अधिक केवल द्वारा प्रभावी बना सकती है: और, के आगे जाना है और उसे कुछ अतिरिक्त बूट करने के लिए हास्केल-y बनाने के लिए, एक सूची समझ से परहेज करते हैं सीमा में divisors की जांच [2..sqrt एन]।

कुछ इस तरह (आप शायद कुछ स्थानीय अनुकूलन कर सकता है अगर आप इसे और अधिक के बारे में सोचा):

*Main> (sum.divisors) 10000000 
14902280 
(4.24 secs, 521136312 bytes) 

*Main> (sum.divisors') 10000000 
14902280 
(0.02 secs, 1625620 bytes) 

:

divisors' n = (1:) $ nub $ concat [ [x, div n x] | x <- [2..limit], rem n x == 0 ] 
    where limit = (floor.sqrt.fromIntegral) n 

कहाँ divisors पिछले कार्यान्वयन है, और divisors 'नए एक है

नोट: हमने किसी भी पुनरावृत्ति को हटाने के लिए नब का उपयोग किया, वास्तव में केवल एक ही संभव पुनरावृत्ति सीमा होगी, यदि एन वर्ग संख्या है। आप इस मामले को बेहतर तरीके से संभालने से थोड़ा अधिक कुशल बना सकते हैं, लेकिन मुझे लगता है कि यह तरीका अधिक पठनीय है (यदि चलने का समय महत्वपूर्ण नहीं है)।