पायथन में प्राइम नंबर खोजने के लिए विभिन्न तरीकों का विश्लेषण

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

सभी भाजक जांचें

यह एक स्ट्रेट फॉरवर्ड प्रोग्राम है जहां हम दी गई संख्या से 1 से एक तक प्रत्येक पूर्णांक लेते हैं और यह जांचते रहते हैं कि संख्या इनमें से किसी से विभाजित होती है या नहीं। यदि कोई संख्या नहीं मिलती है जो इस संख्या को विभाजित कर सकती है तो संख्या अभाज्य है।

उदाहरण

import time
#Function to check Prime Number
def check_prime(final_val):
   if final_val <= 1:
      return False
   for divisor in range(2,final_val):
      if final_val % divisor == 0:
         return False
      return True
# Track the Start Time
StartTime = time.time()
#Count the number of prime numbers
cnt = 0
for final_val in range(1,10001):
   x = check_prime(final_val)
   cnt += x
print 'Count of prime numbers till',final_val,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

आउटपुट

उपरोक्त कोड को चलाने से हमें निम्नलिखित परिणाम मिलते हैं -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 2.3100001812

वर्गमूल तक के कारक(N)

गणितीय रूप से यह भी पाया जाता है कि जिस संख्या की हम जाँच कर रहे हैं, उसके वर्गमूल तक गुणनखंड ज्ञात करना पर्याप्त है। यह दृष्टिकोण पुनरावृत्तियों की संख्या को कम करता है और इसलिए तेज़ होना चाहिए जिसे हम नीचे देख सकते हैं। इस विचार को लागू करने का तर्क नीचे है।

हम उस संख्या का वर्गमूल ज्ञात करते हैं जिसे अभाज्य मान के लिए जाँचा जा रहा है।
हम प्रत्येक मान के साथ संख्या को 2 से शुरू होने वाले वर्गमूल मान तक विभाजित करते हैं, यह जांचने के लिए कि कोई शेष बचा है या नहीं।
यदि उपरोक्त में किसी भी चरण पर शेष शेष शून्य है, तो संख्या अभाज्य नहीं है।

उदाहरण

import math
import time
def is_prime(final_val):
   # 1 is not a prime number
   if final_val <= 1:
      return False
   i = 2
   while i <= math.floor(math.sqrt(final_val)):
   # Check if any remainders are cerated
      if final_val % i == 0:
         return False
      i += 1
   return True
# Track the Start Time
StartTime = time.time()
cnt = 0
for n in xrange(1, 10001):
   x = is_prime(n)
   cnt += x
print 'Count of prime numbers till',n,'is ', cnt
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

आउटपुट

उपरोक्त कोड को चलाने से हमें निम्नलिखित परिणाम मिलते हैं -

Count of prime numbers till 10000 is 1229
Time Elapsed is: 0.0529999732971

इरेटोस्थनीज की छलनी

इस विधि में हम अभाज्य संख्याओं को अभाज्य संख्या तक प्राप्त करने के लिए अभाज्य या भाज्य संख्याओं को हटा देते हैं। तो इसे प्राप्त करने के लिए हम नीचे दिए गए चरणों का पालन करते हैं।

2 से उस संख्या तक के क्रमागत पूर्णांकों की सूची बनाइए जहाँ तक हम सभी अभाज्य संख्याएँ ज्ञात करना चाहते हैं।
पहली संख्या अर्थात् 2 लीजिए और उसके सभी गुणजों की सूची बनाइए। गुणकों की इस सूची को मूल सूची से हटा दें, लेकिन 2 को नहीं। इसे अगली संख्या के लिए दोहराएं, यानी 3 और इसी तरह अगली संख्याओं के लिए। कृपया ध्यान दें कि हम केवल गुणकों को हटा रहे हैं, न कि संख्या को। तो 5 या 11 कभी खत्म नहीं होते लेकिन 10 और 22 खत्म हो जाते हैं।
सभी एलिमिनेशन के बाद बची हुई सूची पूछी गई संख्या तक अभाज्य संख्याओं की सूची है।

उदाहरण

import time
def sieve_method(n):
#Create a list of prime numbers
   prime_number_list = []
   for i in range(2, n+1):
# Capture the number if it si not in prime list
   if i not in prime_number_list:
      print (i)
# Add the number to the prime list number if it is a multiple
   for j in range(i*i, n+1, i):
      prime_number_list.append(j)
# Track the Start Time
StartTime = time.time()
cnt = 0
print(sieve_method(25))
# Track the End Time
EndTime = time.time()
print 'Time Elapsed is: ', EndTime - StartTime

आउटपुट

उपरोक्त कोड को चलाने से हमें निम्नलिखित परिणाम मिलते हैं -

2
3
5
7
11
13
17
19
23
Time Elapsed is: 0.0