در این قسمت تیم کدگیت را با آموزش تشخیص اعداد اول در پایتون همراهی کنید. ابتدای این آموزش اعداد اول را تعریف خواهیم کرد. در ادامه روشهای مختلف پیاده سازی این الگوریتم را انجام میدهیم. با ما همراه باشید تا این برنامه را به شما معرفی کنیم. در صورت تمایل میتوانید پیشنیازهای این آموزش را نیز مطالعه نمایید:
- تبدیل نوع داده در پایتون
- تابع در پایتون
- دیکشنری در پایتون
- حلقه while در پایتون
- حلقه for در پایتون
- دستور if در پایتون
- لیست در پایتون
تشخیص اعداد اول در پایتون
عدد اول عددی طبیعی بزرگتر از ۱ است که بر هیچ عددی بجز خود و ۱ بخشپذیر نباشد. برای اینکه یک عدد اول را تشخیص دهیم از روشهای مختلفی استفاده میشود فرض کنید n عددی است که میخواهیم اول بودن آن را بررسی کنیم:
- اعداد محدوده 2 تا n/2 بررسی میکنیم. اگر عددی در این محدوده باقیمانده آن بر n برابر با صفر شد (بر n بخشپذیر باشد) n عدد اول نیست در غیر این صورت n اول میباشد.
- استفاده از روش حلقه for
- استفاده از روش بازگشتی
- محدوده 2 تا ریشه دوم n یعنی n√ را بررسی میکنیم. اگر عددی در این محدوده باقیمانده آن بر n برابر با صفر شد (بر n بخشپذیر باشد) n عدد اول نیست در غیر این صورت n اول میباشد. دقت کنید دلیل اینکه تا ریشه دوم عدد n بیشتر جلو نمیرویم در ریاضی اثبات شده و ما در این قسمت جزییات آن را توضیح ندادیم. در صورت تمایل میتوانید این موضوع را جستجو و بررسی کنید.
- استفاده از روش بازگشتی
- استفاده از حلقه While
- استفاده از ماژول math
اعداد اول در پایتون روش اول
ابتدا با کمک حلقه For در محدوده 2 تا n/2 به بررسی اول بودن یک عدد میپردازیم. کد این پیاده سازی به صورت زیر میباشد:
num = 11
if num > 1:
for i in range(2, int(num/2)+1):
if (num % i) == 0:
print(num, "is not a prime number")
break
else:
print(num, "is a prime number")
else:
print(num, "is not a prime number")
متغیر n را تعریف کرده و برابر با 11 قرار دادیم. در ادامه در یک حلقه for محدوده 2 تا n/2 را ایجاد کرده و بر روی اعداد این محدوده تک به تک چرخشی داریم. در حلقه for اگر عددی پیدا شود که بخشپذیر بر n باشد n اول نیست و در خروجی is not a prime number چاپ خواهد شد در غیر این صورت is a prime number چاپ خواهد شد. یک شرط if در خارج حلقه for قرار دارد. این شرط به این دلیل است که اگر عدد n بزرگتر از 1 باشد به بررسی آن پرداخته شود و عدد 1 نیازی به بررسی ندارد.
روش دوم پیاده سازی اعداد اول در پایتون به صورت بازگشتی است:
def Prime(number,itr):
if itr == 1:
return True
if number % itr == 0:
return False
if Prime(number,itr-1) == False:
return False
return True
n = 13
itr = int(n/2)+1
print(Prime(n,itr))
یک تابع نوشتیم به نام Prime که دو ورودی میگیرد. ورودی اول number است و ورودی دوم iter یکی از اعداد محدوده(جهت بررسی بخش پذیری آن بر number). پس از بررسی هر بار یکی از iter کم می شود و مجدداً تابع Prime صدا زده میشود. اگر به عدد 1 رسیدیم یعنی تمام اعداد محدوده بررسی شده و بر number بخشپذیر نبودهاند. پس True توسط تابع Prime بازگردانی می شود در غیر این صورت False بازگردانی میشود.
پیاده سازی روش دوم
ابتدا با کمک حلقه For در محدوده 2 تا ریشه دوم n به بررسی اول بودن یک عدد میپردازیم. کد پیاده سازی اعداد اول در پایتون به صورت زیر میباشد:
from math import sqrt
n = 11
if(n > 1):
for i in range(2, int(sqrt(n)) + 1):
if (n % i == 0):
print(n, "is not a prime number")
break
else:
print(n, "is a prime number")
else:
print(n, "is a prime number")
یک حلقه for نوشتیم اما اینبار با کمک ماژول math محدوده پایان را تا ریشه دوم عدد n قرار دادیم. بقیه کد مانند قسمت قبل است که توضیحات آن ارائه گردید.
روش بازگشتی این قسمت نیز به صورت زیر میباشد:
from math import sqrt
def Prime(number,itr):
if itr == 1:
return True
if number % itr == 0:
return False
if Prime(number,itr-1) == False:
return False
return True
num = 13
itr = int(sqrt(num)+1)
print(Prime(num,itr))
کد بازگشتی اعداد اول در پایتون مانند بخش قبل است و تنها متغیر iter را بجای n/2 برابر با ریشه دوم n قرار دادیم. بقیه کد در بخش قبل بررسی شد.
پیاده سازی این روش با کمک حلقه while به صورت زیر است:
def is_prime(n):
if n < 2:
return False
i = 2
while i*i <= n:
if n % i == 0:
return False
i += 1
return True
print(is_prime(11))
print(is_prime(1))
تابعی نوشتیم به نام is_prime که n را در ورودی دریافت میکند. اگر n اول باشد True در غیر این صورت False بر میگرداند. درون تابع متغیر i را تعریف کردیم. حلقه while تازمانی که i*i کمتر از n باشد به چرخش خود ادامه میدهد. این بدان معنی است که تا زمانی که به ریشه دوم عدد n نرسیدهایم حلقه while ادامه دارد.
با قدرت ادامه بده