برنامه‌ی تشخیص عدد اول در پایتون - چگونه با پایتون برنامه بنویسیم؟ قسمت اول

زمان مطالعه: 13 دقیقه
۱۰ فروردین ۱۳۹۹

برنامه‌ی تشخیص عدد اول در پایتون:

برنامه‌ نویسی برای همه مهم است زیرا هیچ رایانه‌ و یا هر نوع دستگاه دیجیتالی، بدون برنامه‌ نویسی قادر به کارکردن نیست. افراد علاقمند به برنامه نویسی، هنگامی به توانایی کدنویسی دست می‌یابند، که هم آموزش صحیح دیده و هم پشتکار داشته باشند.

شما برای یادگیری پایتون، می‌توانید از مجموعه مقالات آموزش‌ برنامه‌نویسی پایتون استفاده کنید. از این مجموعه مقالات می‌توانید جهت تمرین و یادگیری تکنیک‌های برنامه‌نویسی بهره ببرید. اگر دوست دارید با روش فکر کردن و چگونگی نوشتن یک برنامه‌ی پایتون، بیشتر آشنا شوید، ما را همراهی کنید.

نوشتن برنامه‌ی کاربردی با پایتون:

برنامه‌ای بنویسید که یک عدد صحیح از کاربر بگیرد و در پاسخ اعلام کند که عدد مذکور یک عدد اول است یا خیر؟

برای حل یک مسئله، اول باید بفهمیم که سوال مورد نظر چه چیزی از ما خواسته است. در اینجا ابتدا باید یک عدد صحیح از کاربر بگیریم که با وارد کردن دستور ورودی، آن را انجام می‌دهیم.

برای اطلاعات بیشتر در این مورد، مقاله‌ی ورودی و خروجی در پایتون را مطالعه نمایید.

در قسمت بعدی، از ما خواسته شده که اول بودن، عدد ورودی را بررسی کنیم. که ما نخست باید بدانیم، عدد اول چیست؟ و سپس برای تشخیص آن، از چه الگوریتمی استفاده کنیم؟

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

عدد اول چیست؟

همان‌طور که می‌دانید به صورت خلاصه، عددی را عدد اول گویند که به جز عدد یک و خودش، به هیچ عدد دیگری بخش‌پذیر نباشد.

اگر هر عدد را بر اعداد کوچک‌تر از خودش تقسیم کنیم و فقط به یک بخش‌پذیر باشد، عدد اول است. برای این امر، از الگوریتم‌های مختلفی می‌توان استفاده کرد که در این مقاله، از سه الگوریتم متفاوت برای پیاده سازی برنامه‌ی تشخیص عدد اول در پایتون استفاده می‌کنیم. تا شما کاربرد الگوریتم در برنامه‌نویسی را بهتر درک کنید.

الگوریتم اول

الگوریتم اول برنامه‌ی تشخیص عدد اول در پایتون به این صورت است:

  1. یک عدد بگیر و در number قرار بده.
  2. یک جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها به نام accumulator انتخاب کن و 0 را در آن قرار بده.
  3. یک شمارنده به نام i را انتخاب کن و 1 را در آن قرار بده.
  4. اگر باقیمانده‌ی تقسیم number بر i مساوی 0 باشد، یک واحد به مقدار accumulator اضافه کن.
  5. یک واحد به مقدار i اضافه کن.
  6. اگر مقدار i کوچکتر مساوی number است، به گام 4 برگرد.
  7. اگر مقدار accumulator مساوی 2 است، پیغام "عدد شما، عدد اول است" را چاپ کن و به گام 10 برو.
  8. پیغام "عدد شما، عدد اول نیست" را چاپ کن.
  9. به اجرای الگوریتم خاتمه بده.

نوشتن کد:

ابتدا یک عدد را از کاربر می‌گیریم. برای گرفتن ورودی از کاربر، از دستور input() و برای تبدیل رشته به عدد صحیح از دستور int() استفاده می‌کنیم. عدد ورودی را در متغیر number قرار می‌دهیم. به این صورت:

number =int(input('please input your number: '))

اکنون متغیر accumulator که جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها است، را تعریف می‌کنیم و عدد 0 را به آن اختصاص می‌دهیم. به این صورت:

accumulator = 0

برای تقسیم عدد ورودی بر اعداد کوچک‌تر مساوی خودش، از یک حلقه‌ی تکرار for استفاده می‌کنیم. از آنجا که قصد داریم خود متغیر number نیز در حلقه باشد، یک را به آن اضافه می‌کنیم.

در حلقه، اگر باقیمانده‌ی تقسیم ورودی بر عدد جاری حلقه، برابر صفر بود یکی به متغیر accumulator اضافه می‌کنیم. به این صورت:

for i in range(1, number+1):
    if number % i == 0:
        accumulator +=1

وقتی حلقه‌ی ما به پایان می‌رسد، باید مقدار متغیر accumulator را بررسی کنیم. اگر مساوی 2 بود، پیغام "عدد اول است" و در غیر این‌صورت پیغام " عدد اول نیست" را چاپ می‌کنیم. برای این کار از دستور if-else استفاده می‌کنیم. به این صورت:

if accumulator == 2:
    print('your number is prime')  
else:
    print('your number is not prime')

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

number = int(input('please input your number: '))
accumulator = 0
for i in range(1, number+1):
    if number%i == 0:
        accumulator+=1

if accumulator==2:
    print('your number is prime')
else:
    print('your number is not prime')

الگوریتم دوم:

در الگوریتم اول با استفاده از یک جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها توانستیم برنامه‌ای بنویسیم که عدد اول را تشخیص دهد. اکنون می‌خواهیم از الگوریتمی استفاده کنیم که برای پیاده سازی برنامه‌ی تشخیص عدد اول در پایتون، نیاز به جمع‌کننده‌ی تعداد مقسوم‌علیه‌ها ندارد.

  1. یک عدد بگیر و در number قرار بده.
  2. اگر number کوچک‌تر مساوی یک است، پیغام "عدد شما، عدد اول نیست" را چاپ کن و به گام 8 برو.
  3. یک شمارنده به نام i انتخاب کن و مقدار 2 را در آن قرار بده.
  4. اگر باقیمانده‌ی تقسیم number بر i مساوی 0 است، پیغام "عدد شما، عدد اول نیست" را چاپ کن و به گام 8 برو.
  5. یک واحد به مقدار i اضافه کن.
  6. اگر مقدار i کوچکتر از number / 2 است، به گام 4 برگرد.
  7. پیغام "عدد شما، عدد اول است" را چاپ کن.
  8. به اجرای کد خاتمه بده.

نوشتن کد:

مانند کد قبلی، ابتدا از کاربر یک عدد صحیح می‌گیریم و در متغیر number ذخیره می‌کنیم. به این صورت:

number = int( input('please input your number: '))

با استفاده از دستور شرطی if-else، اگر عدد ورودی بزرگ‌تر از یک باشد، برای بررسی به بلوک if هدایت می‌شود. و اگر عدد یک باشد در بلوک else پیغام "عدد شما، عدد اول نیست" چاپ می‌شود. به این صورت:

if number > 1:
    pass
else:
    print('your number is not prime')

اکنون به سراغ نوشتن کدهای بلوک if می‌رویم. طبق الگوریتم ما باید عدد ورودی را بر اعداد 2 تا نصف خودش، برای بخش‌پذیر بودن بررسی کنیم. پس یک حلقه‌ی تکرار for با دامنه‌ی اعداد از 2 تا عدد ورودی تقسیم بر 2 می‌نویسیم. به این صورت:

for i in range(2 , number // 2):

نکته: از آنجا که الگوریتم خوب، باید بهینه شده باشد، ما عدد ورودی را تا نصف خودش بررسی می‌کنیم. زیرا هر عدد اگر تا نصف خودش بر عددی بخش‌پذیر نباشد، بر اعداد بزرگتر از نصفش نیز، بخش‌پذیر نیست.

در حلقه، اگر باقیمانده‌ی تقسیم عدد ورودی بر i مساوی صفر بود، پیغام " عدد اول نیست" را چاپ می‌کنیم. سپس با استفاده از دستور break برنامه را به پایان می‌رسانیم. به این صورت:

if number % i == 0:
    print('your number is not prime')
    break

نکته: چون عدد یک و number در حلقه نیستند، اگر number بر هر عددی بخش‌پذیر باشد، آن عدد، اول نیست.

پله‌ی آخر:

اما اگر حلقه‌ی for بدون هیچ اتفاقی به پایان برسد، در یک else پیغام "عدد اول است" را چاپ می‌کند. به این صورت:

else:
    print('your number is prime')  

به این طریق ما به کمک الگوریتمی دیگر توانستیم برنامه‌ی پایتون تشخیص عدد اول را بنویسیم. کد این برنامه به این صورت است:

number = int(input('please input your number: '))

if number > 1:
    for i in range(2 , number//2):
        if number % I == 0:
            print('your number is not prime')
            break
    else:
	print('your number is prime')  

else:
    print('your number is not prime')

نکته‌ی حائز اهمیت، این است که الگوریتم دوم به دلیل بررسی number/2، بهینه‌تر و از سرعت بالاتری برخوردار است. پس برای نوشتن برنامه‌هایتان، الگوریتمی استفاده کنید که بهینه‌‌شده باشد، زیرا سرعت اجرای برنامه‌ بیشتر و حافظه کمتری اشغال می‌کند. در الگوریتم بعدی، کد ما بهینه‌تر خواهد شد.

الگوریتم سوم:

در الگوریتم سوم برنامه‌ی تشخیص عدد اول در پایتون قصد داریم از الگوریتمی استفاده کنیم که خیلی بهینه‌شده‌تر و سریع‌تر است. در این الگوریتم به جای آن که تا عدد ورودی بررسی شود، تا جذر عدد ورودی بررسی خواهد شد.

  1. یک عدد بگیر و در number قرار بده.
  2. اگر number کوچک‌تر مساوی 1 است، پیغام "عدد شما، عدد اول نیست" را چاپ کن و به گام 10 برو.
  3. اگر number کوچک‌تر مساوی 3 است، پیغام "عدد شما، عدد اول است" را چاپ کن و به گام 10 برو.
  4. اگر باقیمانده‌ی تقسیم number بر 2 یا باقیمانده‌ی تقسیم number بر 3 مساوی 0 است، پیغام "عدد شما، اول نیست" را چاپ کن و به گام 10 برو.
  5. یک شمارنده به نام i انتخاب کن و عدد 5 را در آن قرار بده.
  6. اگر باقیمانده‌ی تقسیم number بر i یا باقیمانده‌ی تقسیم number بر i+2 مساوی 0 است، پیغام "عدد شما، عدد اول نیست را چاپ کن و به گام 10 برو.
  7. مقدار 6 را به i اضافه کن.
  8. اگر i*i کوچکتر مساوی number است، به گام 6 برگرد.
  9. پیغام "عدد شما، عدد اول است" را چاپ کن.
  10. به اجرای الگوریتم خاتمه بده.

نوشتن کد:

طبق موارد قبلی، ابتدا یک ورودی از کاربر می‌گیریم. به این صورت:

number = int( input('please input your number: '))

براساس الگوریتم، برای آن که برنامه در هر گام به پایان برسد، آن را در حلقه‌ای نوشته که یک‌دور می‌زند. پس ما از یک حلقه‌ی while استفاده می‌کنیم و یک متغیر boolean به نام active با مقدار True تعریف می‌کنیم. به این صورت:

active = True
while active:
    pass

در داخل حلقه، با شرط اول، اگر number کوچک‌تر مساوی یک باشد، پیغام "عدد اول نیست" چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

if  number <= 1  : 
    print('your number is not prime')
    break

با عدم برقراری شرط اول، با شرط دوم، اگر number کوچک‌تر مساوی 3 باشد، پیغام "عدد اول است" چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

if  number <= 3   :
    print('your number is prime')  
    break

با برقرار نبودن شرط دوم، به سراغ نوشتن شرط سوم می‌رویم. اگر باقیمانده‌ی تقسیم‌های number بر 2 یا number بر 3، مساوی 0 باشد، پیغام "عدد اول نیست" چاپ می‌شود. سپس با دستور break از برنامه خارج می‌شود. به این صورت:

if  number % 2 == 0 or number % 3 == 0  : 
    print('your number is not prime')
    break

اکنون به گام 5 الگوریتم می‌رسیم، یک متغیر به نام i تعریف کرده و 5 را به آن اختصاص می‌دهیم. سپس یک حلقه‌ی while می‌نویسیم که تا شرط i*i کوچک‌تر مساوی number باشد، ادامه پیدا می‌کند. به این صورت:

i = 5
while i * i <= number :
    pass

در حلقه، اگر باقیمانده‌ی تقسیم‌های number بر i یا number بر i+2، مساوی 0 باشد، پیغام "عدد اول نیست" را چاپ می‌کند. سپس با دستور break از برنامه خارج می‌شود، در غیر این صورت مقدار 6 را به i اضافه می‌کند. به این صورت:

i = 5
while i * i <= number:
    if  number % i == 0 or number % (i + 2) == 0  :
        print('your number is not prime')
        break
    i = i + 6

پله‌ی آخر:

 اکنون برای آن که حلقه‌ی while اولی به پایان برسد، مقدار متغیر active را به False تغییر می‌دهیم. سپس پیغام "عدد شما، یک عدد اول است" را چاپ می‌کنیم. به این صورت:

active = False
print('your number is prime')  

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

number = int(input('please input your number: '))
active = True
while active:
    if number <= 1: 
        print('your number is not prime')
        break
    if number <= 3: 
        print('your number is prime')  
        break

    if number % 2 == 0 or number % 3 == 0: 
        print('your number is not prime')
        break

    i = 5
    while i * i <= number: 
        if number % i == 0 or number % (i + 2) == 0: 
            print('your number is not prime')
            break
        i = i + 6
    active = False
    print('your number is prime')  

نوشتن تابع تشخیص عدد اول:

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

توضیحات کافی در خصوص هر سه الگوریتم‌ در برنامه‌نویسی دادیم. فقط لازم است بدانید، خروجی تابع ما یک boolean است. اگر عدد ورودی، اول باشد، خروجی True و اگر عدد اول نباشد، خروجی False خواهد بود. کد تابع ما به این صورت خواهد بود:

def isPrime(n) : 
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
  
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while (i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True
# ==================== end of function

number = int( input('please input your number: '))

if isPrime(number) : 
    print('your number is prime')  
else : 
    print('your number is not prime')  

جمع‌بندی:

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

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

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

چه امتیازی به این مقاله می دید؟
نویسنده عبدالرضا مولایی
هیچوقت برای یادگیری دیر نیست؛ همیشه چیزهای جدید برای آموختن وجود دارد.. این دو جمله، همیشه آویزه‌ی گوش منه، چون باعث میشه از یادگیری چیزهای تازه هراسی نداشته باشم.

نظرات کاربران

harez

الگوریتم دوم باگ داره
4 رو بدی بهش prime میده

J.m

سلام , اقا زحمت کشیدید , ولی بهتر نبود کد هاتون رو اول تست میکردید بعد مینوشتید . چون خیلی اشتباه نوشته شده , مثلا در الگوریتم دوم که در اخر که کد ها رو کامل نوشتید ایندنت else زیر for نوشته شده , باید زیر if باشد . اشکال دیگر اینکه جلوی کلمه break پرانتز گذاشتید!!

عبدالرضا مولایی

سلام دوست عزیز، تمامی کدها تست شده است.. درمورد else در for این از ویژگی‌های زبان پایتون است اگر قصد آشنایی بیشتر در این مورد را دارید از این لینک استفاده کنید:
https://book.pythontips.com/en/latest/for_-_else.html
درمورد پرانتز در break نیز در یک مورد، اشتباه تایپی رخ داده. ممنون از اینکه اطلاع دادید.

ارسال دیدگاه
خوشحال میشیم دیدگاه و یا تجربیات خودتون رو با ما در میون بذارید :