python, آموزش قدم به قدم پایتون, پایتون

اعداد اول در پایتون

اعداد اول در پایتون

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

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

عدد اول عددی طبیعی بزرگ‌تر از ۱ است که بر هیچ عددی بجز خود و ۱ بخش‌پذیر نباشد. برای اینکه یک عدد اول را تشخیص دهیم از روش‌های مختلفی استفاده می‌شود فرض کنید 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 ادامه دارد.  

نوشته های مشابه

1 دیدگاه در “اعداد اول در پایتون

  1. علی گفت:

    با قدرت ادامه بده

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *