एक्स से y

Question

द्वारा विभाजित नहीं करने के लिए संख्या से बी को ढूंढना यह एक समस्या है जिसे मैं काफी समय से सोच रहा हूं।

एक्स से वाई तक किसी भी संख्या से विभाजित नहीं होने के लिए सभी संख्याओं को खोजने के लिए सबसे तेज़ तरीका क्या है?

इस पर विचार करें:

मैं 1 से 10 के सभी नंबरों को है कि 2 से 5 इस प्रक्रिया से विभाज्य नहीं कर रहे हैं खोजने के लिए बेहद धीमी गति से हो जाएगा अगर मैं जहां एक रेखीय दृष्टिकोण का उपयोग करना चाहते हैं; इस तरह:

result = [] 
a = 1 
b = 10 
x = 2 
y = 5 
for i in range(a,b): 
    t = False 
    for j in range(x,y): 
     if i%j==0: 
      t = True 
      break 
    if t is False: 
     result.append(i) 
return result 

किसी को भी एक रेखीय समाधान की तुलना में कम गणना समय के साथ ऐसा करने के किसी भी अन्य तरीकों में से पता है?

यदि नहीं, तो किसी को भी देख सकते हैं कि इस ताकत तेजी से किया जा, जैसा कि मैंने इस बिंदु पर खाली हूँ ...

निष्ठा से, जॉन

[संपादित करें]

संख्या की संख्या 0 से> 1, ई + 100

यह ए, बी, एक्स और वाई

के लिए सच है

Answer 1

आपको केवल संभावित divisors की सीमा में प्राइम वैल्यू की जांच करने की आवश्यकता है - उदाहरण के लिए, यदि कोई मान 2 से विभाजित नहीं है, तो यह 2 के किसी भी बहुमत से विभाजित नहीं होगा; इसी तरह हर दूसरे प्राइम और प्राइम एकाधिक के लिए। इस प्रकार आपके उदाहरण में आप 2, 3, 5 देख सकते हैं - आपको 4 की जांच करने की आवश्यकता नहीं है, क्योंकि 4 से विभाजित कुछ भी 2 से विभाजित होना चाहिए। इसलिए, एक तेज़ दृष्टिकोण होगा कि आप जिस भी सीमा में रूचि रखते हैं उसमें प्राइम की गणना करें, और फिर बस गणना करें कि वे कौन से मूल्य विभाजित करते हैं।

एक और गति उस सीमा में प्रत्येक मान को जोड़ना है जिसमें आप रुचि रखते हैं set: जब आपको लगता है कि यह आपकी सीमा में किसी संख्या से विभाजित है, तो इसे सेट से हटा दें। फिर आपको केवल सेट संख्याओं का परीक्षण करना चाहिए जो सेट में रहते हैं - यह आपको कई बार परीक्षण संख्याओं को रोक देगा।

यदि हम इन दो दृष्टिकोणों को जोड़ते हैं, तो हम देखते हैं कि हम सभी मानों के set (उदाहरण में, सभी मान 1 से 10 के साथ एक सेट) बना सकते हैं, और बस अपनी दूसरी श्रेणी में प्रत्येक प्राइम के गुणक को हटा सकते हैं उस सेट से।

संपादित करें: जैसा कि पट्टाशु ने बताया, यह कोई काम नहीं करेगा यदि किसी दिए गए मूल्य को विभाजित करने वाला प्रधान सेट में नहीं है। इसे ठीक करने के लिए, हम उपरोक्त में एक समान एल्गोरिदम लागू कर सकते हैं: set के साथ set में प्रत्येक मान के लिए set बनाएं, इसके सभी गुणांक हटा दें। तो टिप्पणियों में नीचे दिए गए उदाहरण के लिए ([3, 6] के साथ) हम 3 से शुरू करेंगे और सेट में इसके गुणक हटा देंगे - इसलिए 6। इसलिए शेष मूल्यों को हमें परीक्षण करने की आवश्यकता होगी [3, 4, 5] जो हम इस मामले में चाहते हैं।

EDIT2: यहाँ एक वास्तव में ऊपर काट दिया, भद्दा कार्यान्वयन किया है कि अनुकूलित नहीं किया गया है और भयानक चर नाम है:

def find_non_factors(): 
    a = 1 
    b = 1000000 
    x = 200 
    y = 1000 

    z = [True for p in range(x, y+1)] 
    for k, i in enumerate(z): 
     if i: 
      k += x 
      n = 2 
      while n * k < y + 1: 
       z[(n*k) - x] = False 
       n += 1 

    k = {p for p in range(a, b+1)} 

    for p, v in enumerate(z): 
     if v: 
      t = p + x 
      n = 1 
      while n * t < (b + 1): 
       if (n * t) in k: 
        k.remove(n * t) 
       n += 1 

    return k 

उन संख्याओं के साथ अपने मूल कार्यान्वयन की कोशिश करो। यह मेरे कंप्यूटर पर 1 मिनट लगता है। यह कार्यान्वयन 2 सेकंड के भीतर आता है।

Answer 2

अंतिम अनुकूलन चेतावनी: पूर्व-परिपक्व रूप से अनुकूलन न करें। जब भी आप कोड को अनुकूलित करने का प्रयास करते हैं, तो यह सुनिश्चित करने के लिए प्रोफाइल करें कि इसे ऑप्टिमाइज़ेशन की आवश्यकता है, और उसी तरह के डेटा पर ऑप्टिमाइज़ेशन को प्रोफाइल करें जिसे आप ऑप्टिमाइज़ करने के लिए अनुकूलित करना चाहते हैं, यह पुष्टि करने के लिए कि यह एक गति है। लगभग सभी कोड को सही उत्तर देने के लिए अनुकूलन की आवश्यकता नहीं है।

आप छोटे एक्स वाई और बड़े एक-ख के लिए अनुकूलन कर रहे हैं:

, x + 2 ... लंबाई के साथ एक सरणी सभी एक्स से बाहर सबसे कम आम एकाधिक है कि, x + 1 बनाएं y। उदाहरण के लिए, 2, 3, 4, 5 के लिए यह 60 होगा, 120 नहीं।

अब इस सरणी को बूलियन के साथ पॉप्युलेट करें - शुरुआत में प्रत्येक सेल के लिए झूठी, फिर xy में प्रत्येक संख्या के लिए, सरणी में सभी प्रविष्टियों को पॉप्युलेट करें सच के साथ उस संख्या के गुणक हैं।

अब ए-बी में प्रत्येक संख्या के लिए, सरणी मॉड्यूलो सरलीकृत में सूचकांक और यदि यह सत्य है, तो यह गलत है, तो वापसी करें।

आप एक्स से वाई कारकों की संख्या को हटाकर इसे थोड़ा तेज़ कर सकते हैं, जो कि प्रमुख कारक विस्तार सख्त सुपरसैट अन्य नंबरों के प्रमुख कारक विस्तारों के हैं। जिसका मेरा मतलब है - यदि आपके पास 2, 3, 4, 5, 4 2 2 2 सख्त सुपरसैट 2 है तो आप इसे हटा सकते हैं और अब हमारी सरणी लंबाई केवल 30 है। 3, 4, 5, 6 जैसे कुछ के लिए हालांकि, 4 2 * 2 है और 6 3 * 2 - 6 3 का सुपरसेट है इसलिए हम इसे हटाते हैं, लेकिन 4 सब कुछ का सुपरसेट नहीं है इसलिए हम इसे अंदर रखते हैं। एलसीएम 3 * 2 * 2 * 5 = 60 है इस तरह की चीज करने से बड़े एब के लिए कुछ गति मिल जाएगी, और अगर आपको इसकी ज़रूरत है तो आपको सरणी दिशा में जाने की आवश्यकता नहीं होगी।

इसके अलावा, ध्यान रखें कि यदि आप हर बार फ़ंक्शन के पूरे परिणाम का उपयोग नहीं कर रहे हैं - जैसे, शायद कभी-कभी आप केवल निम्नतम मूल्य में रुचि रखते हैं - इसे जनरेटर के रूप में लिखें एक समारोह। इस तरह आप इसे तब तक कॉल कर सकते हैं जब तक आपके पास पर्याप्त संख्या न हो और फिर समय बचाएं।