एक अभाज्य संख्या एक पॉजिटिव इंटीजर है जो केवल 1 या स्वयं से विभाज्य होती है। किसी संख्या के अभाज्य होने या न होने का पता लगाना लंबे समय से एक दिलचस्प प्रोग्रामिंग चुनौती है। इसके अलावा अलग-अलग तरीके हैं और उनकी अलग-अलग दक्षता है। इस लेख में हम तीन ऐसे तरीकों को देखेंगे और आंकेंगे कि उनके निष्पादन के समय के संदर्भ में कौन सा अधिक कुशल है।
सभी भाजक जांचें
यह एक सीधा प्रोग्राम है जहां हम दिए गए संख्या से एक कम तक 1 से हर पूर्णांक लेते हैं और जांचते रहते हैं कि संख्या इनमें से किसी से विभाजित होती है या नहीं। यदि कोई संख्या नहीं मिलती जो इस संख्या को विभाजित कर सके तो संख्या अभाज्य है।
उदाहरण
import time # अभाज्य संख्या जांचने का फ़ंक्शन 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 # प्रारंभ समय ट्रैक करें StartTime = time.time() # अभाज्य संख्याओं की संख्या गिनें 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) # अंत समय ट्रैक करें 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 अभाज्य संख्या नहीं है if final_val <= 1: return False i = 2 while i <= math.floor(math.sqrt(final_val)): # जांचें कि क्या कोई शेष बनता है if final_val % i == 0: return False i += 1 return True # प्रारंभ समय ट्रैक करें StartTime = time.time() cnt = 0 for n in range(1, 10001): x = is_prime(n) cnt += x print('Count of prime numbers till', n, 'is ', cnt) # अंत समय ट्रैक करें EndTime = time.time() print('Time Elapsed is: ', EndTime - StartTime)आउटपुट
उपरोक्त कोड चलाने पर हमें निम्नलिखित परिणाम मिलता है -
Count of prime numbers till 10000 is 1229 Time Elapsed is: 0.0529999732971
एराटोस्थनीज की छलनी
इस विधि में हम एक विशिष्ट संख्या तक अभाज्य संख्या प्राप्त करने के लिए गैर-अभाज्य या मिश्रित संख्याओं को समाप्त करते हैं। तो नीचे वे चरण हैं जिनका हम पालन करते हैं।
उस संख्या तक लगातार पूर्णांकों की एक सूची बनाएं जिस तक हम सभी अभाज्य संख्या ढूंढना चाहते हैं।
पहली संख्या यानी 2 लें और इसके सभी गुणकों की एक सूची बनाएं। इस गुणकों की सूची को मूल सूची से हटा दें लेकिन 2 को नहीं। अगली संख्या यानी 3 के लिए इसे दोहराएं और इसी तरह अगली संख्याओं के लिए। कृपया ध्यान दें कि हम केवल गुणकों को हटा रहे हैं न कि संख्या को स्वयं। इसलिए 5 या 11 कभी नहीं हटाए जाते लेकिन 10 और 22 हट जाते हैं।
सभी निष्कासन के बाद बची हुई सूची पूछी गई संख्या तक की अभाज्य संख्याओं की सूची है।
उदाहरण
import time def sieve_method(n): # अभाज्य संख्याओं की सूची बनाएं prime_number_list = [] for i in range(2, n+1): # संख्या को कैप्चर करें यदि यह अभाज्य सूची में नहीं है if i not in prime_number_list: print(i) # संख्या को अभाज्य सूची में जोड़ें यदि यह एक गुणक है for j in range(i*i, n+1, i): prime_number_list.append(j) # प्रारंभ समय ट्रैक करें StartTime = time.time() cnt = 0 print(sieve_method(25)) # अंत समय ट्रैक करें EndTime = time.time() print('Time Elapsed is: ', EndTime - StartTime)आउटपुट
उपरोक्त कोड चलाने पर हमें निम्नलिखित परिणाम मिलता है -
2 3 5 7 11 13 17 19 23 Time Elapsed is: 0.0
