क्या कोई शायद मुझे सिखा सकता है कि इस 'प्रिंट को एनएच प्राइम नंबर' स्क्रिप्ट पर कैसे अनुकूलित किया जाए?

Question

मैं 17 साल की उम्र में पाइथन प्रोग्रामिंग भाषा की मदद से प्रोग्रामिंग के साथ शुरुआत कर रहा हूं।

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

100000 प्राइम संख्याओं की गणना करने और प्रदर्शित करने की कोशिश करने के लिए स्क्रिप्ट को लगभग 6 सेकंड तक रोकना पड़ता है क्योंकि यह प्रिम्स सूची को कंसोल पर आउटपुट के रूप में वापस करने से पहले प्राइम के साथ सूची को पॉप्युलेट करता है।

मैं

print odd, 

का उपयोग कर बस हर पाया अभाज्य संख्या है, जो तेजी से n = 1000 जैसे छोटे आदानों के लिए है मुद्रित करने के लिए के साथ प्रयोग किया गया है, लेकिन एन = 1000000 सूची के लिए अपने आप में बहुत तेजी से प्रिंट (दोनों पायथन खोल और कंसोल में)।

शायद संपूर्ण कोड/एल्गोरिदम को संशोधित किया जाना चाहिए, लेकिन लिपि अनिवार्य रूप से वही रहनी चाहिए: उपयोगकर्ता मुद्रित होने के लिए प्राइम संख्याओं की संख्या में टाइप करता है (एन) और स्क्रिप्ट सभी प्रमुख संख्याओं को एनएच प्राइम तक लौटाती है नंबर।

from time import time 
odd = 1 
primes = [2] 
n = input("Number of prime numbers to print: ") 
clock = time() 
def isPrime(number): 
    global primes 
    for i in primes: 
     if i*i > number: 
      return True 
     if number%i is 0: 
      return False 
while len(primes) < n: 
    odd += 2 
    if isPrime(odd): 
     primes += [odd] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

मैं एटकिन की चलनी की तरह एक चलनी उपयोग करने के लिए पूरी स्क्रिप्ट पुनर्लेखन करना चाहते हो सकता है: http://en.wikipedia.org/wiki/Sieve_of_Atkin

हालांकि, मैं बस अजगर पर अभी शुरुआत कर रहा हूँ (या यहां तक ​​कि प्रोग्रामिंग में: मैं कोड केवल 2 लिखना शुरू किया हफ्ते पहले) और पाइथन में एटकिन एल्गोरिदम की एक चलनी को कोड करने के तरीके के बारे में पता लगाने के लिए यह एक चुनौती होगी।

मैं हर पर :(

Answer 1

एक साधारण अनुकूलन जो कोड पूरी तरह से हैकिंग के बिना लागू किया जा सकता।

• मैं एक गूगल हैकर बाहर इस तरह सामान के माध्यम से मुझे पकड़ वहाँ हाथ होगा इच्छा * मैं प्रधानमंत्री बहुत बेकार सूची अब हो जाता है के रूप में हो जाता है। इसके बजाय पाश और पाश अंदर यह मान के खिलाफ परीक्षण के बाहर मैं का वर्गमूल गणना।

कैसे कभी भी वर्ग रूट स्वयं और महंगी गणना है और उम्मीदवारों के बहुमत को निचले प्राइम (3,5,7) में से एक द्वारा विभाजित किया जाएगा, इसलिए यह इतना अच्छा अनुकूलन (निराशाजनकता) नहीं है। लेकिन हमें वास्तव में उस सटीक और सरल जांच की आवश्यकता नहीं है कि प्राइम मूल्य के एक तिहाई से भी कम है, वर्ग रूट गणना की कम्प्यूटेशनल लागत के बिना समान प्रभाव पड़ता है, लेकिन अपेक्षाकृत कुछ अनावश्यक खर्च पर परीक्षा।

Answer 2

आप prime sieve इस्तेमाल कर सकते हैं, और एक सरल मोड़ के साथ:

1. पहले प्रधानमंत्री 2 परिभाषित के रूप में आप ऐसा करेंगे, 2 के लिए सबसे बड़ी संख्या में पहुँच (max) सेट;
2. की max+1 से max+n तक लगातार संख्याओं की एक सूची उत्पन्न करें;
3. इस सूची में प्राइम के साथ चलनी का प्रयोग करें। जब घुसपैठ करते हैं, तो प्रत्येक प्राइम के लिए प्रारंभिक संख्या को सूची में सबसे छोटी संख्या में सेट करें जिसे प्राइम द्वारा विभाजित किया जा सकता है;
4. यदि राशि रीकर नहीं है, तो गोटो 2।

इस तरह, आप सूची की लंबाई को नियंत्रित कर सकते हैं, और जैसे ही लंबाई बढ़ती है, गति तेज होगी। हालांकि, यह एल्गोरिदम का कुल पुनर्विक्रय है, और कार्यक्रम के लिए कठिन है।

यहां एक नमूना कोड है, जो काफी कच्चे तेल की है, लेकिन यह केवल मूल के 70% से कम समय लगता है:

from math import sqrt 
from time import time 
primes = [2] 
max = 3 
n = input("Number of prime numbers to print: ") 
r=2 
clock = time() 
def sieve(r): 
    global primes 
    global max 
    s = set(range(max,max+r)) 
    for i in primes: 
     b=max//i 
     if (b*i<max): 
      b=b+1 
     b=b*i 
     while b<=max+r-1: 
      if b in s: 
       s.remove(b) 
      b=b+i 
    for i in s: 
     primes.append(i) 
while len(primes) < n: 
    r=primes[-1] 
    sieve(r) 
    max=max+r 
primes=primes[0:n] 
print primes 
clock -= time() 
print "\n", -clock 
raw_input() 

इस में सुधार करने के लिए कई तरीके हैं, यह सिर्फ दृष्टिकोण की धारणा से पता चलता ।

इसके अलावा, यह संख्या बड़ी होने पर स्मृति को उड़ा सकती है। मैंने गतिशील सीमा का उपयोग कुछ हद तक राहत देने की कोशिश की।

और यदि आप वास्तव में उत्सुक (और निडर) हैं, तो आप विभिन्न ओपन सोर्स प्रोजेक्ट्स में अधिक जटिल कार्यान्वयन देख सकते हैं। एक उदाहरण पार/जीपी है, जो सी ++ में लिखा गया है, और तेजी से चमक रहा है (अगर मुझे सही याद है तो मैंने 1 मिनट से भी कम समय में 1 से 50000000 का परीक्षण किया)। उन्हें पायथन में अनुवाद करना कठिन हो सकता है, लेकिन शायद आपके लिए नहीं, बल्कि-

Answer 3

5 से 5 के अलावा 5 में से कोई भी संख्या एक प्रमुख नहीं है। तो आप एक बयान दे सकते हैं जो 5 से अधिक 5 से अधिक होने वाले किसी भी नंबर को छोड़ देता है।

Answer 4

जैसा कि पहले से ही ज़ियाओ वी द्वारा कहा गया था, मैं भी एक चाकू कार्यान्वयन का प्रयास करता हूं। एकमात्र चीज जिसे मैं सुधारता हूं, उपयोग किए गए आकार के लिए Prime number theorem का प्रारंभ बिंदु के रूप में उपयोग करना है।

उलटा फ़ंक्शन कंप्यूटिंग शुद्ध पायथन में सीधा नहीं है, लेकिन एक पुनरावृत्ति दृष्टिकोण पर्याप्त होना चाहिए और इस तरह आप एक बहुत अच्छा विचार प्राप्त कर सकते हैं कि चलनी कितनी बड़ी होनी चाहिए। चूंकि मुझे वास्तव में प्रमेय के लिए सबूत याद नहीं हैं और सुबह 6 बजे है, तो किसी और को यह कहने के लिए चिपकना होगा कि प्रमेय किसी भी ऊपरी सीमा की गारंटी देता है जिसका उपयोग बिना सरल चलनी का उपयोग करने के लिए किया जा सकता है इसे बढ़ने के बारे में चिंता करने के लिए। आईआईआरसी दुख की बात नहीं है।

Answer 5

जैसा कि पहले से ही उल्लेख किया गया है, प्रस्तुत एल्गोरिदम को काफी सुधार नहीं किया जा सकता है। यदि एक तेज समाधान का अनुरोध किया जाता है तो Eratosthenes चलनी उचित है। यदि n >= x/(ln x + 2) का उपयोग कर चाकू का आकार estimated हो सकता है। न्यूटन के पुनरावृत्ति का उपयोग करके इस समीकरण को हल किया जा सकता है। प्रस्तुत एल्गोरिदम मूल रूप से लगभग 10 गुना तेज है:

def sieveSize(n): 
    # computes x such that pi(x) >= n (assumes x >= 55) 
    x = 1.5 * n # start 
    y = x - n * math.log(x) - 2 * n 
    while abs(y) > 0.1: 
     derivative = 1 - n/x 
     x = x - y/derivative 
     y = x - n * math.log(x) - 2 * n 
    return int(x) + 1 

def eratosthenes(n): 
    # create a string flags: flags[i]=='1' iff i prime 
    size = sieveSize(n) 
    flags = ['1'] * size # start with: all numbers are prime 
    flags[0] = flags[1] = '0' # 0 and 1 are not primes 
    i = 0 
    while i * i < size: 
     if flags[i] == '1': 
      for j in range(i * i, size, i): 
       flags[j] = '0' 
     i += 1 
    return flags 

def primes(n): 
    flags = eratosthenes(n) 
    prims = [] 
    for i in range(0, len(flags)): 
     if flags[i] == '1': 
      prims.append(i) 
    return prims 

prims = primes(100000)