प्राइम नंबर खोजने के लिए एल्गोरिथम

प्राइम नंबर खोजने के लिए एल्गोरिथ्म का अनुकूलन

2 3 5 7 11 13 17 19 23 29 31 ... $ 250,000 ...

यह एक लंबे समय से पहले, विश्वविद्यालय में था, जब हमने पास्कल प्रोग्रामिंग भाषा का अध्ययन करना शुरू किया था और होमवर्क को प्राइम नंबर खोजने के लिए एक एल्गोरिथ्म बनाना था।

एल्गोरिथ्म का आविष्कार किया गया था और फिर अध्ययन की जा रही भाषा में लागू किया गया था। कार्यक्रम ने उपयोगकर्ता से नंबर एन के लिए कहा और एन समावेशी तक के सभी अपराधों की तलाश की। पहली सफल परीक्षा के बाद, एक अपरिवर्तनीय इच्छा तुरंत एन = "कई" पेश करने के लिए उठी। कार्यक्रम ने काम किया, लेकिन उतनी तेजी से नहीं जितना हम चाहेंगे। स्वाभाविक रूप से, मामला कई जांचों में था (एन * एन / 2 के आदेश का), इसलिए मुझे अनावश्यक लोगों से छुटकारा पाना था। नतीजतन, 5 समान एल्गोरिदम निकले, जिनमें से प्रत्येक ने पिछले एक की तुलना में तेजी से काम किया। हाल ही में मैं उन्हें याद करना और लागू करना चाहता था, लेकिन इस बार अजगर में।

तो चलिए चलते हैं। छात्र के सिर पर आने वाला पहला एल्गोरिथ्म लिस्टिंग 1 में दिखाया गया है।

#  1 #  N n = input("n=") #        lst = [] #  k     k = 0 #     2  N for i in xrange(2, n+1): #     2   for j in xrange(2, i): #    if i % j == 0: k = k + 1 #   ,     if k == 0: lst.append(i) else: k = 0 #     print lst 

आपको बहुत जल्दी पता चलता है कि प्रत्येक संख्या के विभाजकों को गिनने की कोई आवश्यकता नहीं है और इसलिए चर k को उसके कर्तव्यों से मुक्त किया जा सकता है। वास्तव में, यदि कम से कम एक भाजक मौजूद है, तो संख्या अब प्राइम नहीं है। सूची 2 देखें।

 #  2 n = input("n=") lst = [] for i in xrange(2, n+1): for j in xrange(2, i): if i % j == 0: #   ,   . break else: lst.append(i) print lst 

ब्रेक का निर्माण हमें आंतरिक लूप को पूरा करने और बाहरी लूप के अगले पुनरावृत्ति पर जाने की अनुमति देता है।
फिर सवाल उठता है: "यदि संख्या 2 से विभाज्य नहीं है तो 4 से क्यों विभाजित करें?"। हम निष्कर्ष निकालते हैं कि आपको लाभांश से अधिक नहीं होने वाले अपराधों के बीच विभाजक की खोज करने की आवश्यकता है। हमारे एल्गोरिथ्म में बदल जाता है ... सूची 3 देखें।

 #  3 n = input("n=") lst=[] for i in xrange(2, n+1): #    (lst)   for j in lst: if i % j == 0: break else: lst.append(i) print lst 

और फिर हम संख्याओं के सिद्धांत को याद करते हैं और समझते हैं कि हमें केवल उन संख्याओं को हल करने की आवश्यकता है जो मांगी गई जड़ से अधिक नहीं हैं। उदाहरण के लिए, यदि संख्या M में एक विभाजक पाई है, तो एक भाजक qi है जैसे कि pi * qi = M. अर्थात, एक जोड़ी को खोजने के लिए, यह एक छोटे को खोजने के लिए पर्याप्त है। सभी जोड़ियों में, सबसे छोटी जोड़ी के साथ अपेक्षित जोड़ी समान पाई और क्यूई के साथ जोड़ी है, अर्थात, pi * pi = M => pi = sqrt (M)। सूची 4 देखें।

 #  4 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

N = 10000 के साथ लिस्टिंग 4 में कोड बहुत पहले विकल्प की तुलना में लगभग 1000 गुना तेज है। एक और "त्वरक" है, केवल उन संख्याओं की जांच करें जो 1, 3, 7 या 9 में समाप्त होती हैं (चूंकि बाकी स्पष्ट रूप से 2 या 5 से विभाज्य हैं)। सूची 5 देखें।

 #  5 from math import sqrt n = input("n=") lst=[] for i in xrange(2, n+1): if (i > 10): if (i%2==0) or (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

लिस्टिंग 5 में एक मामूली बदलाव के परिणामस्वरूप, हमें गति में थोड़ी वृद्धि हुई है:

 #  6 from math import sqrt n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j > int((sqrt(i)) + 1): lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

कुल: अंतिम लिस्टिंग से कार्यक्रम मूल संस्करण की तुलना में लगभग 1300 गुना तेज चलता है।
मैंने खुद को इस समस्या को जल्द से जल्द हल करने के लिए एक कार्यक्रम लिखने का कार्य निर्धारित नहीं किया, यह नौसिखिए प्रोग्रामर के लिए एक प्रदर्शन है जो आपके कार्यक्रमों को अनुकूलित करने में एक सही ढंग से रचित एल्गोरिथ्म एक महत्वपूर्ण भूमिका निभाता है।

पुनश्च
टिप्पणियों के लिए धन्यवाद, हम सूची 7 प्राप्त करते हैं:

 #  7 n = input("n=") lst=[2] for i in xrange(3, n+1, 2): if (i > 10) and (i%10==5): continue for j in lst: if j*j-1 > i: lst.append(i) break if (i % j == 0): break else: lst.append(i) print lst 

N = 10000 पर, हम समय सीखते हैं:
समय 1 = 26.24
समय 2 = 3.113
समय 3 = 0.413
समय 4 = 0.096
समय 5 = 0.087
समय 6 = 0.083
समय 7 = 0.053

एराटोस्थनीज की चलनी:

 #  8 n = input("n=") a = range(n+1) a[1] = 0 lst = [] i = 2 while i <= n: if a[i] != 0: lst.append(a[i]) for j in xrange(i, n+1, i): a[j] = 0 i += 1 print lst 

N = 1,000,000 के लिए परिणाम:
समय 7 = 7.088
समय 8 = 1.143