प्राइम की गणना करना और सूची में शामिल होना

Question

मैंने हाल ही में पाइथन का उपयोग करके प्रोजेक्ट यूलर पर समस्याओं को हल करने का प्रयास करना शुरू कर दिया है, और प्राइम की गणना करने और उन्हें सूची में जोड़ने की कोशिश करते समय इस सड़क पर टक्कर मार दी है। मैंने निम्नलिखित कोड लिखा है, लेकिन मैं उलझन में हूं कि जब मैं इसे चलाता हूं तो यह कुछ भी आउटपुट क्यों नहीं करता है।

import math 

primes = [] 

def isPrime(i): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 
print(primes) 

Answer 1

प्रयास करें:

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(math.sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 

print(primes) 

Answer 2

इस प्रयास करें:

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

for i in range (1, 100): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

print(primes) 

यह काम कर रहा दिखाने के लिए, मैं प्रिंट पहले 100:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Answer 3

एक सशर्त सूची समझ का उपयोग करते हुए:

primes = [ 
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2 # Anything less than 2 is not prime. 
    and i % 2 # No evens (except for 2 above) 
    and all(i % n for n in range(3, int(i ** 0.5) + 1))] 

>>> primes[:10] 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

>>> primes[-10:] 
[9999889, 
9999901, 
9999907, 
9999929, 
9999931, 
9999937, 
9999943, 
9999971, 
9999973, 
9999991] 

Answer 4

ऐसा करने का सबसे आसान तरीका सिवी नामक कुछ का उपयोग करना है। यहां एक लाख तक सभी प्राइम प्राप्त करने का तरीका बताया गया है।

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 

sieve = [True]*(10**7+1) 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

विचार है कि हम शुरू में sieve नामक सूची बना सकते हैं और जिसका अर्थ है कि हम अब अभाज्य संख्या के रूप में 1 लाख (सम्मिलित) के लिए सभी नंबरों पर विचार के लिए कर रहे हैं True करने के लिए सभी मान निर्दिष्ट है। हम sieve सूची में प्रत्येक संख्या को एक मिलियन से अधिक कर देंगे और False के रूप में इसके प्रत्येक बहुमत को चिह्नित करेंगे। इसके अतिरिक्त, अनुकूलित करने के लिए, हम केवल 1 मिलियन वर्ग वर्ग के लिए पुनरावृत्त करते हैं। ऐसा क्यों? क्योंकि किसी संख्या में दो कारक नहीं हो सकते हैं, जिनमें से दोनों संख्या के वर्ग रूट से अधिक हैं। इसलिए यदि हम अपने वर्ग रूट की छत तक और फिर भी अविभाज्य तक पूर्णांक द्वारा एक संख्या विभाजित करते हैं, तो इसका अर्थ यह है कि इसका एक प्रमुख है।

तो यदि आप यह जांचना चाहते हैं कि कोई संख्या प्रमुख है, तो आप sieve[some_number] का उपयोग कर सकते हैं। अगर यह False लौटाता है तो यह एक प्रमुख नहीं है। आप [x for x in range(len(sieve)) if sieve[x]]

संपादित स्पीड तुलना उपयोग कर सकते हैं अभाज्य संख्या की एक सूची प्राप्त करने के लिए -

import timeit 
import math 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 


# Other approaches 
time_0 = timeit.default_timer() 
primes = [] 
for i in range (1, 10**6+1): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

# Sieve Approach 
time_1 = timeit.default_timer() 
sieve = [True]*(10**6+1) 
sieve[0] = False #because we wont consider zero and one as primes 
sieve[1] = False 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

primes_2 = [x for x in range(len(sieve)) if sieve[x]] 

time_2 = timeit.default_timer() 
time_1-time_0 # 12.423080921173096 seconds 
time_2-time_1 # 0.9901950359344482 seconds 

एक हजार 100 नंबर के लिए, चलनी का उपयोग कर 12 से अधिक गुना तेजी से है। एक मिलियन के लिए यह अनुपात 90 हो जाता है। साथ ही, संख्याओं की संख्या का उपयोग करते समय, मैं सूचियों को जोड़ने के खिलाफ सलाह दूंगा। इसके बजाय, एक सूची शुरू करें और फिर मान असाइन करें।

Answer 5

यदि आप प्राइम्स की एक सूची बना रहे हैं, तो यह आपके समाधान के हिस्से के रूप में उस सूची का उपयोग करने के लिए और अधिक कुशल हो सकता है।

उदाहरण के लिए

, इस पाश:

for i in range(3, int(math.sqrt(number)) + 1): 

प्रधानमंत्री 1009 के लिए 30 नंबर का परीक्षण होगा ~ लेकिन वहाँ केवल 10 अभाज्य संख्या 1009 वर्गमूल है कि वास्तव में जांच की आवश्यकता होती है कम से कम कर रहे हैं। और यह अंतर सिर्फ बढ़ता रहता है। कहीं @ ClockSlave की चलनी के रूप में के रूप में तेजी से

primes = [2] 

for number in range(3, 9999999 + 1, 2): # only test odd numbers 

    for prime in primes: 
     if prime * prime > number: # we're past sqrt, a prime! 
      primes.append(number) 
      break 

     if number % prime == 0: # a composite 
      break 

print(*primes[:10], '...', *primes[-10:]) 

, लेकिन संभावना अन्य समाधान के कई से पहले खत्म हो जाएगा:

हमारी बढ़ती प्रधानमंत्री सूची समाधान के हिस्से के रूप का उपयोग करना।

Answer 6

अब यह काम करता है, मैं 999

import math 

primes = [] 


def isPrime(number): 
    if number <= 1: 
     return False 
    for i in range(2, int(math.sqrt(number)) + 1): 
     if number % i == 0: 
      return False 
    return True 

for i in range(1, 999): 
    if isPrime(i): 
     primes.append(i) 

print(primes) 

[आउटपुट] के लिए संख्या shortned है

[2, 3, 5, 7, 11, 13, 17 , 1 9, 23, 2 9, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 9 7, 101, 103, 107, 109, 113, 127, 131 , 137, 13 9, 14 9, 151, 157, 163, 167, 173, 17 9, 181, 1 9 1, 1 9 3, 1 9 7, 199, 211, 223, 227, 22 9, 233, 23 9, 241, 251, 257, 263, 26 9 , 271, 277, 281, 283, 2 9 3, 307, 311, 313, 317, 331, 337, 34 7, 34 9, 353, 35 9, 367, 373, 37 9, 383, 38 9, 3 9 7, 401, 40 9, 41 9, 421, 431, 433, 43 9, 443, 44 9, 457, 461, 463, 467, 47 9, 487, 491, 4 9, 503, 50 9, 521, 523, 541, 547, 557, 563, 56 9, 571, 577, 587, 5 9 3, 5 9, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 65 9, 661, 673, 677, 683, 691, 701, 70 9, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 7 9 7, 80 9, 811, 821, 823, 827, 829, 839, 853, 857, 85 9, 863, 877, 881, 883, 887, 907, 911, 9 1 9, 9 2 9, 937, 9 41, 9 47, 953, 967, 971, 977, 983, 991, 997]

Answer 7

[0,99 99 999] में सभी प्रमुख संख्याएं प्राप्त करने के लिए आपका एल्गोरिदम बहुत कुशल नहीं है। इसे करने के लिए इसे लंबे समय तक खर्च करने की आवश्यकता है ताकि आप इसे निष्पादित करते समय आउटपुट नहीं देख सकें। ऐसा इसलिए है क्योंकि यह नहीं किया गया है। एक तेज एल्गोरिदम के लिए, आप this