روش تشخیص اینکه یک عدد اول است یا خیر

روش های مختلفی برای اینکار وجود دارد که به ترتیب بهینه بودن و سرعت، از کم تا زیاد، بررسی می کنیم. در این مقاله، کد ها را به زبان پایتون می نویسیم اما روش حل برای تمام زبان ها یکسان است و فقط با سینتکسی متفاوت می توانید آن را در زبان مورد نظر خود پیاده سازی کنید.

اول از همه با تعریف اعداد اول شروع کنیم:

“یک عدد اول عددی است که به غیر از خودش و 1 به هیچ عدد اول دیگری بخش پذیر نباشد.”

روش اول:

در این روش، خیلی ساده عدد مورد نظر را به تمام اعداد کوچکتر از خودش تا عدد 1 تقسیم می کنیم. اگر فقط به 2 عدد بخش پذیر بود (یعنی خودش و 1)، آن عدد اول است.

توجه: این روش فقط برای این است که راه حل اولیه خود را به کد تبدیل کنیم تا ویرایش و بهینه سازی از روی این کد اولیه امکان پذیر باشد و ذهن شما آماده حل این مسئله شود، وگرنه اصلاً استفاده از این الگوریتم را در پروژه های واقعی توصیه نمی کنم. چراکه برای اعداد کمی بزرگ نیز با مشکل مواجه خواهیم شد.

نکته: برای محاسبه بخش پذیر بودن از عملگر % استفاده می کنیم. این عملگر، باقیمانده تقسیم را محاسبه می کند. اگر باقیمانده تقسیم 0 باشد یعنی بخش پذیر است.

def is_prime(num):
   count = 0
   for i in range(1, num+1):
      if num % i == 0:
         count = count + 1
   if count == 2:
      return True
   else:
      return False

روش دوم:

در این روش می خواهیم کمی کد را بهینه تر کنیم. همانطور که گفتیم اگر عددی به یکی از اعداد غیر از 1 و خود عدد بخش پذیر باشد اول نیست. پس برای اعداد غیر اول نیازی نیست که کل اعداد محاسبه شود. اولین عددی (غیر از 1 و خود عدد) که پیدا شد که عدد ما بر آن بخش پذیر بود، دیگر نیاز نیست که بقیه اعداد چک شوند و عدد مورد نظر اول نیست.

1. برای پیاده سازی این روش در کد، از دستور break استفاده می کنیم. به این معنی که در هر جایی از حلقه، اگر عدد ما به یکی از اعداد بخش پذیر شد، دیگر حلقه ادامه پیدا نکند.
2. برای مشخص شدن اول بودن یا نبودن نیز از متغیری boolean به نام isPrime استفاده می کنیم. فرض اولیه این است که عدد اول است پس مقدار این متغیر را برابر با True قرار می دهیم. اگر در طول حلقه for با یک پخشپذیری مواجه شدیم مقدار این متغیر را False می کنیم.
3. بر خلاف قبلی، حلقه را از 2 تا یک عدد قبل از عدد اصلی ادامه می دهیم. تا اعداد بخش پذیر غیر از این دو عدد پیدا شوند.
4. اگر عدد اصلی 0 یا 1 باشد اول نیست و اگر 2 باشد اول است و این اعداد نباید به حلقه وارد شوند. پس قبل از شروع حلقه تکلیف این اعداد را مشخص می کنیم.

def is_prime(num):
   if num == 0 or num == 1:
      return False
   elif num == 2:
      return True

   isPrime = True
   for i in range(2, num):
      if num % i == 0:
         isPrime = False
         break
   return isPrime

توجه: در صورتی که کد های بالا را در کامپایلر آنلاین سایت اجرا کنید خواهید دید که با سرعت خیلی خوبی اجرا خواهند شد. شاید از خود بپرسید که چه دلیلی برای بهینه سازی این کد ها وجود دارد؟ علت این است که گاهی کد ها به این سادگی نخواهد بود. مثلاً در تمرین پیدا کردن 10001 مین عدد اول باید از عدد 2 یکی یکی کد های بالا برای هر عدد محاسبه شود تا اعداد اول مشخص شوند. سپس تا وقتی که تعداد اعداد اول پیدا شده به 10001 برسد باید اینکار ادامه پیدا کند. و با الگوریتم های بالا این کار امکان پذیر نیست و یا به شدت کند اجرا می شود.

روش سوم

از روش سوم به بعد، با بررسی دقیق تر اعدادی که در حلقه قرار می گیرند، قصد داریم باز هم تعداد اعدادی که بررسی می شوند را کم کنیم.

عدد 36 را در نظر بگیرید. مشخص است که به خاطر زوج بودن اول نیست. یعنی به 2 بخش پذیر است. اما ضرایب زیر را در نظر بگیرید:

36 = 1 * 36
36 = 2 * 18
36 = 3 * 12
36 = 4 * 9
36 = 6 * 6
36 = 9 * 4
36 = 12 * 3
36 = 18 * 2
36 = 36 * 1

همانطور که می بینید از عدد 6 به بعد مقسوم علیه ها تکرار می شوند. فقط جای آنها عوض می شود. یعنی اگر برای بررسی بخش پذیری از عدد 1 تا 6 را بررسی کنیم کافی است، چرا که بعد از 6، اعدادی بررسی می شوند که قبلاً بررسی شده اند. در مورد همه اعداد این قانون پابرجاست. اگر عددی از اعداد 1 تا جذر خودش به هیچ عددی بخش پذیر نباشد یعنی به اعداد بعد از آن نیز بخش پذیر نیست.

پس در روش سوم فقط طول حلقه را کاهش می دهیم و فقط اعداد 2 تا جذر عدد اصلی را بررسی می کنیم:

from math import sqrt
def is_prime(num):
   if num == 0 or num == 1:
      return False
   elif num == 2:
      return True
    
   isPrime = True
   for i in range(2, int(sqrt(num)) + 1):
      if num % i == 0:
         isPrime = False
         break
   return isPrime

روش چهارم (بهترین، سریعترین و بهینه ترین روش):

اگر عددی به 2 بخش پذیر نباشد، به 4 و 6 و 8 و … نیز بخش پذیر نیست. پس نیازی نیست این اعداد در حلقه قرار داشته باشند. در نتیجه می توانیم فقط اعداد فرد را در حلقه داشته باشیم.

برای اینکار ابتدا خارج از حلقه، عدد 2 را بررسی می کنیم. اگر عددی به 2 بخش پذیر باشد، اول نیست (اعداد زوج غیر از خود 2). سپس در حلقه range فقط اعداد فرد را بررسی می کنیم:

from math import sqrt
def is_prime(num):
   if num == 0 or num == 1:
      return False
   elif num == 2:
      return True

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