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

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

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

پیاده‌سازی را گام‌به‌گام با روش‌های پایه، یعنی شمارش مقسوم‌علیه‌ها و استفاده از متغیر کمکی، شروع می‌کنیم. سپس با رفع خطاهای رایجی مانند باگ عدد ۴، به سراغ روش‌های بهینه‌تر می‌رویم: بررسی تا جذر عدد، قاعده [فرمول] ، توابع بازگشتی، کتابخانه SymPy و غربال اراتوستن.

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

در مسیر یادگیری برنامه‌نویسی، تحلیل مسئله و تبدیل تعریف ریاضی آن به شرط‌های منطقی، اولین قدم پیش از نوشتن کد است. عدد اول (Prime Number) عددی طبیعی و بزرگ‌تر از ۱ است که جز بر ۱ و خودش، بر هیچ عدد دیگری بخش‌پذیر نیست؛ یعنی دقیقاً دو مقسوم‌علیه دارد. با این تعریف، اعداد منفی، ۰ و ۱ اول نیستند. عدد ۱ خارج از تعریف اعداد اول قرار می‌گیرد و عدد ۲ کوچک‌ترین عدد اول در ریاضیات است. برای تشخیص اول بودن عدد در پایتون، باقی‌مانده تقسیم عدد ورودی بر اعداد کوچک‌تر از خودش را با عملگر % بررسی می‌کنیم:

# نمونه‌های ورودی و خروجی مورد انتظار در برنامه
Input: n = 11 -> Output: True (Prime Number - فقط بر 1 و 11 بخش‌پذیر است)
Input: n = 15 -> Output: False (Not a Prime Number - بر 3 و 5 هم بخش‌پذیر است)
Input: n = 1  -> Output: False (Not a Prime Number - کوچک‌تر از 2 است)

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

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

آموزش ۱۵۰ تمرین پایتون از مبتدی تا حرفه‌ای

549,000 219,600 تومان

60%

مشاهده و خرید

روش اول: شمارش مقسوم‌علیه‌ها (مناسب شروع یادگیری)

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

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')

دستور input() ابتدا ورودی را دریافت می‌کند و int() آن را به عدد صحیح تبدیل می‌کند. شرط اول، اعداد کوچک‌تر از ۲ را رد می‌کند. سپس برنامه متغیر شمارنده accumulator را با مقدار اولیه ۰ تعریف می‌کند. حلقه for بازه ۱ تا number + ۱ را پیمایش می‌کند؛ البته تابع range حد بالا را در بازه نمی‌آورد. هر بار که شرط number % i == ۰ برقرار باشد، حلقه یک واحد به شمارنده اضافه می‌کند. این الگوریتم بهینه نیست، زیرا حتی اگر عدد بر ۲ بخش‌پذیر باشد، حلقه باز هم تا انتهای عدد پیش می‌رود.

روش دوم: استفاده از متغیر کمکی (Flag) و دستور break

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

number = int(input("Enter a number: "))
flag = False

if number > 1:
    for i in range(2, number):
        if (number % i) == 0:
            flag = True
            break

    if flag:
        print(number, "is not a prime number")
    else:
        print(number, "is a prime number")
else:
    print(number, "is not a prime number")

در این کد، متغیر کمکی flag با مقدار اولیه False تعریف می‌شود. حلقه، اعداد ۲ تا یکی مانده به خود عدد را بررسی می‌کند. اگر باقی‌مانده تقسیم صفر شود، flag مقدار True می‌گیرد و دستور break بلافاصله حلقه را متوقف می‌کند تا تکرارهای اضافی انجام نشوند.

روش سوم: کاهش بازه بررسی تا نصف عدد ( [فرمول] ) و رفع باگ عدد ۴

هیچ عددی بر مقادیر بزرگ‌تر از نصف خودش، جز خود آن عدد، بخش‌پذیر نیست. پس لازم نیست حلقه را تا number – ۱ ادامه دهیم و می‌توانیم بازه بررسی را به نصف عدد، یعنی number // ۲، محدود کنیم. ساختار for-else در پایتون نیز به ما امکان می‌دهد متغیر flag را حذف کنیم:

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')

چرا دستور else اول هم‌تراز با حلقه for نوشته شده است؟

در پایتون، بلوک else که با حلقه for هم‌تراز است و Indentation یکسانی دارد، به ساختار خود حلقه تعلق دارد. این بلوک فقط زمانی اجرا می‌شود که حلقه به طور کامل به پایان برسد و با دستور break متوقف نشده باشد؛ یعنی هیچ مقسوم‌علیهی پیدا نشود. else دوم با if number > ۱ هم‌تراز است و زمانی اجرا می‌شود که عدد ورودی ۱ یا کمتر باشد.

اشکال‌زدایی باگ عدد ۴:

اگر هنگام تعریف بازه حلقه، عبارت + ۱ را ننویسید و از range(۲, number // ۲) استفاده کنید، برنامه عدد ۴ را به اشتباه اول تشخیص می‌دهد. برای این ورودی، حاصل ۴ // ۲ برابر ۲ است و بازه به شکل range(۲, ۲) درمی‌آید. تابع range حد بالا را در بازه نمی‌آورد، پس این بازه خالی است. در نتیجه، حلقه اصلاً اجرا نمی‌شود و برنامه مستقیماً وارد بخش else می‌شود و ۴ را اول اعلام می‌کند. اضافه کردن + ۱ به حد بالا در عبارت number // ۲ + ۱ تضمین می‌کند که عدد ۲ نیز در حلقه بررسی شود.

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

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

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

بررسی مقسوم‌علیه‌ها تا جذر عدد ( [فرمول] )

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

n = 11

if n <= 1:
    print(False)
else:
    prime = True
    for i in range(2, int(n  0.5) + 1):
        if n % i == 0:
            prime = False
            break
    print(prime)

عبارت n ** ۰.۵ جذر عدد را محاسبه می‌کند و تابع int() بخش اعشاری آن را حذف می‌کند. افزودن + ۱ نیز باعث می‌شود خود عدد جذر در بازه range قرار بگیرد و بررسی شود. برای عددی مانند ۱۰۰، این روش به جای ۵۰ بار تکرار در روش نصف عدد، حداکثر تا عدد ۱۰ را بررسی می‌کند.

الگوریتم بهینه [فرمول] (سریع‌ترین روش حلقه)

علاوه بر محدود کردن بازه به جذر عدد، می‌توانیم گام حرکت حلقه را هم بزرگ‌تر کنیم. در ریاضیات، تمام اعداد صحیح را می‌توان به شکل [فرمول] (برای [فرمول] از [فرمول] تا [فرمول] ) نوشت. اعداد با فرم [فرمول] ، [فرمول] و [فرمول] بر ۲ بخش‌پذیرند و اعداد با فرم [فرمول] بر ۳ بخش‌پذیرند. در نتیجه، تمام اعداد اول به استثنای ۲ و ۳، به شکل [فرمول] هستند.

برای استفاده از این قاعده، ابتدا بخش‌پذیری عدد بر ۲ و ۳ را بررسی می‌کنیم. سپس حلقه فقط اعداد دارای فرم [فرمول] را تا جذر عدد بررسی می‌کند:

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')

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

1. ابتدا برنامه اعداد کوچک‌تر یا مساوی ۱ را غیراول و اعداد ۲ و ۳ را اول تشخیص می‌دهد.
2. سپس بخش‌پذیری بر ۲ و ۳ را بررسی می‌کند تا تمام مضارب زوج و مضارب ۳ را حذف کند.
3. شمارنده i از عدد ۵ (یعنی [فرمول] ) شروع می‌شود. شرط i * i <= number حلقه را به بازه تا جذر عدد محدود می‌کند.
4. در هر تکرار، حلقه بخش‌پذیری عدد بر i ( [فرمول] ) و i + ۲ ( [فرمول] ) را بررسی می‌کند. سپس شمارنده ۶ واحد افزایش می‌یابد (i += ۶).

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

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

آموزش رایگان توابع در پایتون

رایگان

مشاهده

نوشتن تابع استاندارد is_prime

با قرار دادن الگوریتم بهینه [فرمول] در قالب تابع، کدی خواهیم داشت که یک عدد را به عنوان ورودی می‌گیرد و مقدار بولین برمی‌گرداند: True برای عدد اول و False برای عدد غیراول.

def is_prime(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

# تست تابع
number = int(input('please input your number: '))
if is_prime(number):
    print('your number is prime')
else:
    print('your number is not prime')

دستور return به محض مشخص شدن نتیجه، اجرای تابع را متوقف می‌کند و مقدار بولین را برمی‌گرداند. به همین دلیل، در این تابع دیگر به متغیرهای کمکی active یا is_prime و دستور break نیاز نداریم.

برای اعداد کوچک می‌توان از قابلیت‌های خلاصه‌نویسی پایتون، یعنی List Comprehension و تابع sum، استفاده کرد و تابع را در یک خط نوشت. امکان ترکیب آن با تابع لامبدا در پایتون نیز وجود دارد:

def p(n):
    return n > 1 and not sum([1 for i in range(2, n) if n % i == 0]) > 0

print(p(11))
# Output: True

تشخیص عدد اول به روش بازگشتی (Recursion)

در روش بازگشتی، تابع به جای استفاده از حلقه for یا while، خودش را با مقسوم‌علیهی کوچک‌تر فراخوانی می‌کند تا به شرط پایه برسد. برای محاسبه جذر عدد در شروع کار، تابع sqrt را با دستور import در پایتون از ماژول math فراخوانی می‌کنیم:

from math import sqrt

def prime(n, i):
    if n <= 1:
        return False
    if i == 1:
        return True
    if n % i == 0:
        return False
    return prime(n, i - 1)

n = 13
print(prime(n, int(sqrt(n))))
# Output: True

تابع در اولین فراخوانی، مقدار n و بخش صحیح جذر آن را به عنوان مقسوم‌علیه i دریافت می‌کند. اگر n بر i بخش‌پذیر باشد، تابع False برمی‌گرداند. در غیر این صورت، دوباره خودش را با مقدار i – ۱ فراخوانی می‌کند. اگر i به ۱ برسد و هیچ مقسوم‌علیهی پیدا نشود، عدد اول است و تابع مقدار True را برمی‌گرداند.

مطالب مرتبط

همه چیز در مورد توابع بازگشتی پایتون

استفاده از کتابخانه آماده SymPy

اگر در پروژه‌ای علمی یا ریاضی کار می‌کنید و به نوشتن دستی الگوریتم نیاز ندارید، کتابخانه sympy تابع آماده و بهینه‌ای به نام isprime در اختیار شما قرار می‌دهد:

from sympy import isprime

n = 13
print(isprime(n))
# Output: True

برای اجرای این کد، کتابخانه SymPy باید از قبل با دستور pip install sympy در محیط پایتون شما نصب شده باشد.

چاپ اعداد اول در پایتون (در یک بازه یا کوچک‌تر از n)

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

چاپ اعداد اول در یک بازه مشخص با حلقه‌های تودرتو

برای پیدا کردن اعداد اول بین دو عدد، مثلاً از ۹۰۰ تا ۱۰۰۰، می‌توانیم دو حلقه for تودرتو بنویسیم. حلقه بیرونی اعداد بازه را پیمایش می‌کند و حلقه درونی اول بودن هر عدد را می‌سنجد:

lower = 900
upper = 1000

print("Prime numbers between", lower, "and", upper, "are:")

for num in range(lower, upper + 1):
    if num > 1:
        for i in range(2, int(num  0.5) + 1):
            if (num % i) == 0:
                break
        else:
            print(num)

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

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

def find_primes_in_range(lower, upper):
    primes = []
    for num in range(lower, upper + 1):
        if is_prime(num):
            primes.append(num)
    return primes

print(find_primes_in_range(10, 50))
# Output: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

آموزش جامع پایتون

799,000 439,450 تومان

45%

مشاهده و خرید

برنامه اعداد اول کوچکتر از n در پایتون با الگوریتم غربال اراتوستن

برای پیدا کردن تمام اعداد اول کوچک‌تر یا مساوی یک عدد مشخص ( [فرمول] )، بررسی تک‌تک اعداد با حلقه کند است. «غربال اراتوستن» (Sieve of Eratosthenes) یکی از سریع‌ترین روش‌های کلاسیک برای این کار است. این الگوریتم به جای بررسی بخش‌پذیری هر عدد، مضارب اعداد اول را حذف می‌کند:

1. لیستی از تمام اعداد ۰ تا [فرمول] در نظر می‌گیریم و فرض می‌کنیم همه آن‌ها اول هستند (True).
2. اعداد ۰ و ۱ را خط می‌زنیم (False).
3. از عدد ۲ شروع می‌کنیم. خود ۲ اول است، اما تمام مضارب آن، یعنی ۴، ۶، ۸ و… را خط می‌زنیم.
4. عدد خط‌نخورده بعدی، یعنی ۳، را انتخاب می‌کنیم و تمام مضارب آن را از جدول حذف می‌کنیم.
5. این کار را تا رسیدن به جذر عدد [فرمول] تکرار می‌کنیم. تمام اعدادی که در پایان خط نخورده باقی بمانند، اول هستند.

کد پایتون این الگوریتم به این صورت است:

def sieve_of_eratosthenes(max_num):
    primes = []
    is_prime = [True] * (max_num + 1)
    is_prime[0] = is_prime[1] = False

    for num in range(2, int(max_num  0.5) + 1):
        if is_prime[num]:
            for multiple in range(num * num, max_num + 1, num):
                is_prime[multiple] = False

    for num in range(2, max_num + 1):
        if is_prime[num]:
            primes.append(num)

    return primes

max_number = 50
primes_list = sieve_of_eratosthenes(max_number)
print(f"Prime numbers up to {max_number}: {primes_list}")
# Output: Prime numbers up to 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

حلقه داخلی، خط زدن مضارب هر عدد را از num * num شروع می‌کند، زیرا اعداد اول قبلی، مضارب کوچک‌تر را قبلاً خط زده‌اند. پس از پایان این کار، برنامه هر اندیسی را که مقدار آن در لیست بولین همچنان True است، با متد append در پایتون به لیست نهایی primes اضافه می‌کند و این لیست را برمی‌گرداند.

نکات تکمیلی برای بهبود و تست کد

برای اینکه برنامه تشخیص عدد اول در پروژه‌های واقعی درست کار کند و با خطا مواجه نشود، باید این چهار نکته را رعایت کنید:

• الگوریتم را متناسب با نیاز انتخاب کنید. برای بررسی اول بودن یک عدد، تابع مبتنی بر جذر یا الگوریتم [فرمول] مناسب‌ترین انتخاب است. اگر به لیستی از اعداد اول تا سقف مشخصی نیاز دارید، از غربال اراتوستن استفاده کنید تا محاسبه جذر برای تک‌تک اعداد تکرار نشود.
• در پروژه‌های عملی، خروجی را به صورت ساختار داده برگردانید. به جای چاپ مستقیم عبارت «عدد اول است» با print، تابع باید مقدار بولین (True/False) یا لیستی از اعداد اول را برگرداند تا بخش‌های دیگر کد بتوانند آن را پردازش کنند.
• ورودی‌ها و موارد خاص را پیش از ورود به حلقه اصلی مدیریت کنید. کد شما باید در برابر ورودی‌های نامناسب، مانند اعداد منفی، صفر، یک یا رشته‌های متنی در input، ایمن باشد.
• پس از نوشتن تابع، با تست واحد (Unit Testing) عملکرد آن را جداگانه آزمایش کنید. برای این کار از اعداد مرزی و چالش‌برانگیز استفاده کنید: عدد ۱، عدد غیراول مرزی؛ عدد ۲، تنها عدد اول زوج؛ عدد ۴، برای اطمینان از صحت بازه range؛ و عدد ۲۵، اولین عدد مرکب در الگوریتم [فرمول] که مضرب ۵ است. آزمایش این ورودی‌ها خطاهای منطقی کد را مشخص می‌کند.

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

——