পাইথনে প্রাইম নম্বর খুঁজে বের করার জন্য বিভিন্ন পদ্ধতির বিশ্লেষণ

একটি মৌলিক সংখ্যা একটি ধনাত্মক পূর্ণসংখ্যা যা শুধুমাত্র 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

Eratosthenes এর চালনি

এই পদ্ধতিতে আমরা নির্দিষ্ট সংখ্যা পর্যন্ত মৌলিক সংখ্যা পেতে নন-প্রাইম বা যৌগিক সংখ্যাগুলিকে বাদ দিই। তাই নিচের ধাপগুলো আমরা তা অর্জন করতে অনুসরণ করি।

• 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