क्या कोई मुझे एरेटोस्टेनेस स्क्रिप्ट की इस चलनी को समझने में मदद कर सकता है? आखिरी जोड़ी लाइनों ने मुझे

Question

स्टंप किया है ठीक है, इसलिए मुझे एराटोस्टेनेस की चलनी के पीछे सिद्धांत मिलता है। मैंने कोशिश की, और काफी हद तक असफल रहा, खुद को लिखने के लिए (मैंने एक कार्यात्मक प्रधान संख्या जनरेटर लिखा था, यह सिर्फ कुशल या चाकू नहीं था)। मुझे लगता है कि मुझे गणित को समझने में कोई समस्या है, लेकिन प्रोग्रामिंग ने मुझे भी मिश्रित किया है।

import numpy as np 

def primesfrom2to(n): 
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool) 
    # print(sieve) for n = 10 returns [True, True, True] 

ठीक है, बल्ले को लिखो मैं थोड़ा उलझन में हूं। यह सच्चे मूल्यों की एक सूची उत्पन्न कर रहा है जो प्रगतिशील रूप से झूठी चिह्नित की जाएगी क्योंकि वे समग्र होने के लिए निर्धारित हैं। मुझे लगता है कि यह कह रहा है कि एन से कम मूल्यों में से 1/3 से अधिक मूल्य प्राइम नहीं होंगे, लेकिन मॉड्यूलस ऑपरेशन को क्या जोड़ना है?

sieve[0] = False 

अंक 1 के रूप में चिह्नित?

for i in range(int(n**0.5)//3+1): 
     # print(i) for n = 10 returns 0 and 1 on separate lines 

यह जांच करने के लिए सीमा निर्धारित कर रहा है। किसी भी संख्या में इसके वर्ग रूट से अधिक उत्पाद नहीं है। 3+1 द्वारा विभाजित करने के साथ क्या हो रहा है?

 if sieve[i]: 
      k=3*i+1|1 
      #print(k) for n = 10 returns '5' doesn't change till it adds 7 at n = 50 

ठीक है तो, अगर sieve[i] सच है (ताकि प्रधानमंत्री/अभी तक समग्र रूप में चिह्नित नहीं?) तो 3*i + 1 or 1? यह वास्तव में कैसे काम करता है? ऐसा लगता है कि यह बाद के उत्पादों को हटाने के लिए गुणा किया जाएगा, लेकिन मुझे नहीं पता कि कैसे।

  sieve[  ((k*k)/3)  ::2*k] = False 
      sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False 

ठीक तो इन दोनों को अभाज्य संख्या k ले जा रहे हैं और उन सभी आगे गुणकों अंकन? यदि n=5 यह sieve[8.33::10] = False नहीं करेगा? और दूसरा sieve[41.3::10] जैसा है? मुझे यह बिलकुल समझ में नहीं आया।

print(np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]) 

ठीक है, और अंत में वास्तव में प्राइम्स की सूची उत्पन्न करता है। फिर, तीन से गुणा करने के साथ क्या हो रहा है? स्पष्ट रूप से इस कोड में लगभग 3 मूलभूत कुछ है जो मुझे नहीं मिलता है। इसके अलावा मैं |1 अवधारणा को फिर से समझने में विफल रहा हूं।

ओह और बस मस्ती के लिए यहां मेरा प्रभावी और बेहद अक्षम प्रयास है।

import numpy 
def sieve(num): 

    master = numpy.array([i for i in range(2, num+1)]) 
    run = [] 
    y=2 


    while y <= ((num+1)**(1/2)): 
     thing = [x for x in range(y, num+1, y) if x > 5 or x == 4] 
     run = run + thing 
     y = y+1 
    alist = numpy.in1d(master, run, invert = True) 
    blist = (master[alist]) 
    print(blist) 

500,000 तक की कीमतों की गणना करने में 57 वें स्थान पर गए। मैं 2,000,000 तक की समस्या के युलर योग कर रहा था।

Answer 1

यहाँ numpy में एक साधारण चलनी एल्गोरिथ्म है:

import numpy as np 
def sieve(Nmax): 
    """Calculate prime numbers between 0 and Nmax-1.""" 
    is_prime = np.ones(Nmax, dtype=bool) 
    Pmax = int(np.sqrt(Nmax)+1) 
    is_prime[0] = is_prime[1] = False 
    p = 2 
    dp = 1 
    while p <= Pmax: 
     if is_prime[p]: 
      is_prime[p*2::p] = False 
     p += dp 
     dp = 2 
    primes = np.argwhere(is_prime)[:,0] 
    print(primes) 

sieve(100)  

अगर मैं प्रिंट बयान निकालने के लिए, यह nmax के लिए = 10^8 मेरी मामूली लैपटॉप पर चलता है 2.5 सेकंड में।

यह एल्गोरिदम थोड़ा अक्षम है क्योंकि इसे मूल्यों और गुणकों के प्राइम-नेस को स्टोर करने की आवश्यकता है। आप उन्हें फ़िल्टर करके स्टोरेज स्पेस पर सहेज सकते हैं, ताकि आप एन के प्राइम-एनस का ट्रैक रख सकें * 6 + 1 और एन * 6 + 5, किसी भी पूर्णांक n> = 1 के लिए। इससे आपको थोड़ी अधिक पुस्तक-रखरखाव की कीमत पर स्टोरेज स्पेस के दो तिहाई बचाए जाते हैं। ऐसा लगता है कि आपने कठिन संस्करण से शुरुआत करने का प्रयास किया था। इसके अलावा, सभी बहीखाता महंगा हो जाती है यदि इसमें पाइथन दुभाषिया if कथन का मूल्यांकन करता है और आपकी सूचियों का मेमोरी प्रबंधन करता है। पायथन/numpy की सरणी टुकड़ा करने के लिए यह एक और अधिक प्राकृतिक तरीका है, और यह शायद आपके उद्देश्यों के लिए पर्याप्त तेज़ है।

आपके प्रश्नों के बारे में:

• (n% 6 == 2) बूलियन, 0 या 1 के रूप में व्याख्या की जाएगी और एक "बंद-एक करके" त्रुटि को रोकने के लिए एक और तत्व जोड़ नहीं है।
• int(n**0.5)//3+1int(int(n**0.5)/3) + 1 के रूप में पढ़ा जाना चाहिए। डिवीजन अतिरिक्त से पहले चला जाता है। तीन से विभाजन यह है कि आप केवल 6 एन + 1 और 6 एन + 5 मानों के लिए स्थान आवंटित करते हैं।
• k=3*i+1|1 का अर्थ है k=3*i+1, अगर यह भी है तो यह जोड़ें (यह थोड़ा-सा है या)। ऐरे तत्व 'i' संभावित प्राइम संख्या (3*i+1)|1 से मेल खाता है। इसलिए यदि सरणी सूचकांक [0, 1, 2, 3, 4, 5, ...] हैं, तो वे [1, 5, 7, 11, 13, 17, ...] संख्याओं का प्रतिनिधित्व करते हैं।
• चावल तत्वों को गलत तरीके से सेट करना 6n + 1 और 6n + 5 का प्रतिनिधित्व करने वाले तत्वों के लिए अलग से किया जाता है, यही कारण है कि दो असाइनमेंट हैं।
• यदि आप इसे पायथन 2.7 में चला रहे हैं, तो पूर्णांक विभाजन हमेशा छोटा कर दिया जाता है, इसलिए 9/2 परिणामस्वरूप 4 होगा। पायथन 3 में, // ऑपरेटर का पूर्णांक डिवीजनों के लिए उपयोग करना बेहतर होगा, यानी (k*k)/3 होना चाहिए (k*k)//3।

संपादित करें: आप उस एल्गोरिदम को विशेषता देना चाहेंगे जो आप पूछ रहे थे: Fastest way to list all primes below N।