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

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

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

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

برای حل هر مسئله برنامه‌نویسی، ابتدا باید دقیقاً بدانیم مسئله چه چیزی از ما می‌خواهد. در اینجا دو مرحله اصلی داریم:

• دریافت یک عدد صحیح از کاربر
• بررسی اول بودن یا نبودن عدد وارد شده

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

عدد اول چیست؟

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

• 2، 3، 5 و 7 عدد اول هستند.
• 4، 6 و 9 عدد اول نیستند.

برای تشخیص عدد اول، می‌توان عدد موردنظر را بر اعداد کوچک‌تر یا مساوی خودش تقسیم کرد و تعداد مقسوم‌علیه‌های آن را بررسی نمود.

الگوریتم چیست؟

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

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

الگوریتم اول: روش شمارش مقسوم‌علیه‌ها

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

الگوریتم به این صورت عمل می‌کند:

• یک عدد دریافت کن و آن را در متغیر number قرار بده.
• یک متغیر شمارنده به نام accumulator تعریف کن و مقدار اولیه آن را 0 بگذار.
• با یک شمارنده (i) از 1 تا number حرکت کن.
• اگر number بر i بخش‌پذیر بود، مقدار accumulator را یک واحد افزایش بده.
• مقدار i را یک واحد افزایش بده.
• اگر مقدار i کوچک‌تر یا مساوی number بود، به مرحله 4 برگرد.
• اگر مقدار accumulator برابر 2 بود، پیغام «عدد وارد شده عدد اول است» را نمایش بده.
• در غیر این صورت، پیغام «عدد وارد شده عدد اول نیست» را نمایش بده.
• اجرای الگوریتم را به پایان برسان.

پیاده‌سازی الگوریتم اول در پایتون

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

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

سپس متغیر شمارنده مقسوم‌علیه‌ها را تعریف می‌کنیم و عدد 0 را به آن اختصاص می‌دهیم:

accumulator = 0

حال با استفاده از یک حلقه for، عدد ورودی را بر تمام اعداد از 1 تا خودش تقسیم می‌کنیم.

در حلقه، اگر باقیمانده‌ی تقسیم ورودی بر عدد جاری حلقه، برابر صفر بود یکی به متغیر 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')

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

number = int(input('Please enter a number: '))
if number < 2:
    print('Your number is not prime')
else:
    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')

الگوریتم دوم: استفاده از جمع‌کننده تعداد مقسوم‌علیه‌ها

در الگوریتم اول با استفاده از یک «جمع‌کننده تعداد مقسوم‌علیه‌ها» توانستیم تشخیص دهیم یک عدد اول است یا نه. حالا می‌خواهیم از روشی استفاده کنیم که نیازی به شمارش تعداد مقسوم‌علیه‌ها ندارد و به‌جای آن، فقط بررسی می‌کند آیا عدد ورودی مقسوم‌علیه‌ای غیر از ۱ و خودش دارد یا نه.

ایده اصلی: اگر عددی (بزرگ‌تر از ۱) حتی یک مقسوم‌علیه بین ۲ تا نصف خودش داشته باشد، «اول نیست».

مراحل الگوریتم

• یک عدد بگیر و آن را در number قرار بده.
• اگر number کوچک‌تر یا مساوی ۱ بود، پیام «عدد شما عدد اول نیست» را چاپ کن و پایان بده.
• یک شمارنده به نام i انتخاب کن و مقدار ۲ را در آن قرار بده.
• اگر باقیمانده تقسیم number بر i برابر ۰ بود، پیام «عدد شما عدد اول نیست» را چاپ کن و پایان بده.
• مقدار i را یک واحد افزایش بده.
• اگر i کوچک‌تر یا مساوی number / 2 بود، به مرحله ۴ برگرد.
• اگر هیچ مقسوم‌علیه‌ای پیدا نشد، پیام «عدد شما عدد اول است» را چاپ کن.
• پایان.

پیاده‌سازی الگوریتم دوم در پایتون

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

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

سپس با یک شرط ساده بررسی می‌کنیم که آیا عدد ورودی اصلاً «می‌تواند» اول باشد یا نه. (عددهای ۰ و ۱ اول نیستند.)

if number <= 1:
    print('your number is not prime')
else:
    # ادامه بررسی در این قسمت انجام می‌شود
    pass

اکنون وارد بخش اصلی می‌شویم. طبق الگوریتم، باید number را بر عددهای ۲ تا نصف خودش بررسی کنیم. بنابراین یک حلقه for می‌نویسیم:

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

اگر حلقه بدون پیدا کردن مقسوم‌علیه تمام شود، یعنی عدد اول است. اینجا else مربوط به حلقه for است:

else:
    print('your number is prime')

اشکال‌زدایی کد

در این الگوریتم، هنگام وارد کردن عدد ۴، برنامه به‌اشتباه آن را عدد اول تشخیص می‌دهد. دلیل این مشکل، نحوه تعریف بازه حلقه for است، نه خود تقسیم بر ۲. در پایتون، تابع range حد بالایی را شامل نمی‌شود.
بنابراین در این خط:

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

اگر number برابر ۴ باشد، مقدار number // 2 برابر ۲ می‌شود و در نتیجه حلقه به‌صورت زیر اجرا می‌شود:

range(2, 2)

این بازه خالی است و حلقه اصلاً اجرا نمی‌شود. به همین دلیل، برنامه مستقیماً وارد بخش else حلقه شده و عدد ۴ را به اشتباه «عدد اول» در نظر می‌گیرد.

برای جلوگیری از این مشکل، می‌توان بازه حلقه را طوری تعریف کرد که عدد ۲ نیز بررسی شود. کافی است حد بالای بازه را یک واحد افزایش دهیم:

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

با این تغییر، برای عدد ۴، حلقه به‌درستی مقدار i = 2 را بررسی می‌کند و عدد ۴ به‌عنوان عدد اول شناسایی نخواهد شد.

کد اصلاح‌شده الگوریتم دوم

number = int(input('please input your number: '))
if number > 1:
    for i in range(2, number // 2 + 1):
        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، فقط تا نصف آن بررسی انجام می‌دهد. هرچه الگوریتم بهینه‌تر باشد، سرعت اجرای برنامه بیشتر و مصرف منابع کمتر خواهد بود.

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

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

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

مراحل الگوریتم

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

• یک عدد دریافت کن و آن را در متغیر number قرار بده.
• اگر number کوچک‌تر یا مساوی ۱ بود، عدد اول نیست.
• اگر number کوچک‌تر یا مساوی ۳ بود، عدد اول است.
• اگر number بر ۲ یا ۳ بخش‌پذیر بود، عدد اول نیست.
• یک شمارنده به نام i تعریف کن و مقدار اولیه آن را ۵ قرار بده.
• اگر number بر i یا i + 2 بخش‌پذیر بود، عدد اول نیست.
• مقدار i را ۶ واحد افزایش بده.
• اگر i × i کوچک‌تر یا مساوی number بود، به گام ۶ برگرد.
• در غیر این صورت، عدد اول است.
• اجرای الگوریتم پایان می‌یابد.

نکته مهم: بعد از بررسی ۲ و ۳، تنها اعدادی که به صورت 6k ± 1 هستند می‌توانند عدد اول باشند؛ به همین دلیل در هر تکرار، ۶ واحد به i اضافه می‌شود.

پیاده‌سازی الگوریتم سوم در پایتون

مانند الگوریتم‌های قبلی، ابتدا عدد را از کاربر دریافت می‌کنیم:

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

برای کنترل جریان اجرای برنامه و خروج در زمان مناسب، از یک حلقه while استفاده می‌کنیم که فقط یک‌بار اجرا می‌شود:

active = True
while active:
    pass

بررسی شرط‌های پایه: ابتدا ساده‌ترین حالت‌ها را بررسی می‌کنیم:

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

اگر عدد بزرگ‌تر از ۱ باشد، شرط بعدی بررسی می‌شود:

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

با برقرار نبودن شرط دوم، سراغ شرط سوم می‌رویم. اگر عدد number بر 2 یا 3 بخش‌پذیر باشد (یعنی باقی‌مانده تقسیم صفر شود)، عدد اول نیست. در این حالت پیام مربوط چاپ می‌شود و با دستور 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 یا i+2 بخش‌پذیر باشد، عدد اول نیست. در این حالت پیام چاپ می‌شود و یک متغیر کمکی را False می‌کنیم تا بعد از خروج از حلقه، به اشتباه «prime» چاپ نشود. در غیر این صورت، مقدار i را 6 واحد زیاد می‌کنیم:

i = 5
is_prime = True
while i * i <= number:
    if number % i == 0 or number % (i + 2) == 0:
        print('your number is not prime')
        is_prime = False
        break
    i += 6اگر تا اینجا عدد «اول نیست» تشخیص داده نشده باشد، یعنی عدد اول است. برای پایان دادن به حلقه اصلی، مقدار active را False می‌کنیم و سپس پیام مناسب را چاپ می‌کنیم:

اگر تا اینجا عدد «اول نیست» تشخیص داده نشده باشد، یعنی عدد اول است. برای پایان دادن به حلقه اصلی، مقدار 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
    is_prime = True
    while i * i <= number:
        if number % i == 0 or number % (i + 2) == 0:
            print('your number is not prime')
            is_prime = False
            break
        i += 6
    active = False
    if is_prime:
        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')  

چاپ اعداد ۱ تا ۱۰۰ به‌جز مضارب عدد ۴ در پایتون

در این تمرین، می‌خواهیم برنامه‌ای بنویسیم که تمام اعداد بین ۱ تا ۱۰۰ را چاپ کند، اما اگر عددی بر ۴ بخش‌پذیر بود (مضرب ۴ بود)، آن عدد در خروجی نمایش داده نشود.

این مثال تمرین بسیار خوبی برای یادگیری هم‌زمان موارد زیر است:

• حلقه تکرار (for)
• عملگر باقیمانده (%)
• شرط (if)
• مفهوم بخش‌پذیری در برنامه‌نویسی

تحلیل مسئله

صورت مسئله از ما سه چیز می‌خواهد:

• تولید اعداد از ۱ تا ۱۰۰
• بررسی بخش‌پذیر بودن هر عدد بر ۴
• چاپ فقط عددهایی که بر ۴ بخش‌پذیر نیستند

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

الگوریتم حل مسئله

الگوریتم به‌صورت مرحله‌به‌مرحله به شکل زیر است:

• یک حلقه از ۱ تا ۱۰۰ ایجاد کن.
• در هر تکرار، بررسی کن آیا عدد بر ۴ بخش‌پذیر است یا نه.
• اگر عدد بر ۴ بخش‌پذیر نبود، آن را چاپ کن.
• اگر بخش‌پذیر بود، از چاپ آن صرف‌نظر کن.

پیاده‌سازی در پایتون

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

for i in range(1, 101):
    if i % 4 != 0:
        print(i)

توضیح خط‌به‌خط کد

• range(1, 101): اعداد ۱ تا ۱۰۰ را تولید می‌کند (عدد ۱۰۱ در نظر گرفته نمی‌شود).
• i % 4 != 0: بررسی می‌کند که باقیمانده تقسیم عدد بر ۴ صفر نباشد؛ یعنی عدد مضرب ۴ نباشد.
• print(i): فقط اعدادی را چاپ می‌کند که شرط بالا را داشته باشند.

نکته مهم: اگر شرط را به شکل زیر می‌نوشتیم:

if i % 4 == 0:
    continue

و سپس print(i) را خارج از شرط قرار می‌دادیم، نتیجه دقیقاً مشابه می‌شد.

جمع بندی

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

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

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