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

۷۲۰۸ بازدید
آخرین به‌روزرسانی: ۱۸ اردیبهشت ۱۴۰۲
زمان مطالعه: ۳ دقیقه
برنامه تشخیص اعداد اول در پایتون — به زبان ساده

«عدد اول» (Prime Numbers)، عددی طبیعی و بزرگ‌تر از یک است که جز یک و خودش، بر هیچ عدد دیگری بخش‌پذیر نباشد. برای مطالعه بیشتر پیرامون اعداد اول، مطلب «اعداد اول — به زبان ساده» توصیه می‌شود. در این مطلب، هدف ارائه روشی برای نوشتن برنامه تشخیص اعداد اول در پایتون است. برای تشخیص اعداد اول، راهکارهای گوناگونی وجود دارد که یکی از محبوب‌ترین آن‌ها، ‌«غربال اراتوستن» (Sieve of Eratosthenes) است. غربال اراتوستن، یکی از روش‌های باستانی برای یافتن همه اعداد اول کوچک‌تر از یک عدد مشخص (مثلا n) است. روش کار به این صورت است که اعداد اول (از دو تا جذر n) یافته می‌شوند و مضارب آن‌ها (غیر از خودشان) خط می‌خورند. اعداد خط نخورده، همگی اول هستند. برای مثال، فرض می‌شود هدف پیدا کردن اعداد اول از ۱ تا n = ۱۰۰ است. با استفاده از غربال اراتوستن، به صورت زیر عمل می‌شود:

  1. همه اعداد از ۱ تا ۱۰۰ را می‌نویسیم.
  2. عدد ۱ را خط می‌زنیم.
  3. دور عدد ۲ خط می‌کشیم (عدد اول است) و همه مضرب‌هایش را خط می‌زنیم.
  4. دور عدد اول بعدی (در اینجا ۳) خط می‌کشیم و همه مضرب‌هایش را خط می‌زنیم.
  5. به مرحله ۴ باز می‌گردیم و آن مرحله را تکرار می‌کنیم.
  6. مراحل بالا را تا جایی که عدد اولی پیدا شود که مضرب‌هایش در جدول خط نخورده باشد، ادامه می‌دهیم.
  7. اعداد باقی‌مانده (که خط نخورده‌اند) عدد اول هستند.

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

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

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

فرض می‌شود عدد صحیح مثبت N داده شده است. هدف، نوشتن برنامه‌ای در پایتون است که تعیین می‌کند یک عدد اول است یا خیر. عدد اول، یک عدد طبیعی بزرگ‌تر از ۱ است که به جز خودش و ۱، هیچ مقسوم‌علیه مثبت دیگری ندارد. اولین اعداد اول عبارتند از {... ,11 ,7 ,5 ,3 , 2}.

مثال:

ورودی: n=11

خروجی: درست (true)



ورودی: n=15

خروجی: غلط (false)



ورودی: n=1

خروجی: غلط (false)

در حال حاضر، هدف حل کردن این مساله به وسیله روش تکرار شونده است. کار به این صورت انجام می‌شود که با شروع از ۲ تا n/2 و با استفاده از یک حلقه for، تکرار در همه اعداد انجام و بررسی می‌شود که آیا n بر عددی در این بازه تقسیم‌پذیر است یا خیر.

اگر عددی پیدا شد که n بر آن تقسیم‌پذیر بود، مقدار «false» بازگردانده می‌شود. اگر هیچ عددی بین ۲ و n/2 یافت نشد که n بر آن تقسیم‌پذیر باشد، بدین معنا است که n عدد اول است و مقدار «True» بازگردانده می‌شود. در ادامه، برنامه تشخیص اعداد اول در پایتون ارائه شده است.

1# Python program to check if  
2# given number is prime or not 
3  
4num = 11
5  
6# If given number is greater than 1 
7if num > 1: 
8      
9   # Iterate from 2 to n / 2  
10   for i in range(2, num//2): 
11         
12       # If num is divisible by any number between  
13       # 2 and n / 2, it is not prime  
14       if (num % i) == 0: 
15           print(num, "is not a prime number") 
16           break
17   else: 
18       print(num, "is a prime number") 
19  
20else: 
21   print(num, "is not a prime number")

خروجی:

11 is a prime number

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

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

  1. با توجه به اینکه یک عامل بزرگتر از n باید مضرب یک عامل کوچک‌تر باشد که در حال حاضر بررسی شده است، به جای n، تا n√ بررسی می‌شود.
  2. الگوریتم را می‌توان با توجه به اینکه همه اعداد اول به استثنای ۲ و ۳، به شکل 6k ± 1 هستند، بهبود داد. این امر بدین دلیل است که همه اعداد صحیح را می‌توان به صورت 6k + i برای عدد صحیح k و $$i = -1, 0, 1, 2, 3$$ یا ۴، نشان داد. همانطور که پیش‌تر بیان شد، ۲ و ۳ استثنا هستند. عدد ۲ بر (6k + 0) ،(6k + 2) ،(6k + 4) و ۳ بر (6k + 3) بخش‌پذیر است. بنابراین، یک روش کارآمدتر آن است که بررسی شود آیا n بر ۲ یا ۳ بخش‌پذیر است یا نه و سپس، برای همه اعداد به شکل 6k ± 1 بررسی شود.
1# A optimized school method based  
2# Python3 program to check 
3# if a number is prime 
4  
5  
6def isPrime(n) : 
7  
8    # Corner cases 
9    if (n <= 1) : 
10        return False
11    if (n <= 3) : 
12        return True
13  
14    # This is checked so that we can skip  
15    # middle five numbers in below loop 
16    if (n % 2 == 0 or n % 3 == 0) : 
17        return False
18  
19    i = 5
20    while(i * i <= n) : 
21        if (n % i == 0 or n % (i + 2) == 0) : 
22            return False
23        i = i + 6
24  
25    return True
26  
27  
28# Driver Program  
29if (isPrime(11)) : 
30    print(" true") 
31else : 
32    print(" false") 
33      
34if(isPrime(15)) : 
35    print(" true") 
36else :  
37    print(" false") 
38      
39      
40# This code is contributed  
41# by Nikita Tiwari.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۶۶ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۶ دیدگاه برای «برنامه تشخیص اعداد اول در پایتون — به زبان ساده»

خیلی ممنون ولی این برنامه اشتباهه؟ چون اگر i رو از پنج شروع کنیم به 23 که برسیم + 2 میشود 25 که اول نیست

سلام. ممنون از مقاله خوبتون.
فقط یک مشکل هست. وقتی کد اول احرا میگیرم و num=4 وارد میکنم ، جواب true میاد که اشتباهه.


‌با سلام و احترام؛

صمیمانه از همراهی شما با مجله فرادرس و ارائه بازخورد سپاس‌گزاریم.

خروجی تابع به مقدار ورودی بستگی دارد. این برنامه در واقع یک تابع است که مقدار ورودی n را از کاربر دریافت و اول بودن یا نبودن آن را بررسی می‌کند. شما می‌توانید کدها را از اینجا کپی کرده و در سرویس Google Colab اجرا کنید. سپس می‌توانید تابع را آزمایش کنید. به این صورت که مثلاً می‌توانید بعد از اجرای کدهای تابع، یک بلوک کد جدید اضافه و در آن دستور isPrime(25) را وارد و اجرا کنید. در این صورت اگر مقدار ورودی عدد اول باشد، خروجی True و در غیر این صورت، False خواهد بود. ملاحظه خواهید کرد که این تابع یا همان برنامه به درستی کار می‌کند و هیچ اشتباهی در صورت نگرفته است.

برای شما آرزوی سلامتی و موفقیت داریم.

سلام و تشکر رای آموزش
سوال داشتم در برنامه تشخیص عدداول(اولین برنامه)، دو الست دربرنامه هست else اول به کدام if برمیگرده؟ اگه به if دوم که حاصل تقسیم چک میکنه،چرا ازش عقب ترتایپ شده؟ اشکال من چگونگی اجرای حلقه از2 تاریکی مونده به نصف عدد داده شده است//باتشکر

با سلام و احترام؛

صمیمانه از همراهی شما با مجله فرادرس و ارائه بازخورد سپاس‌گزاریم.

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

برای شما آرزوی سلامتی و موفقیت داریم.

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

نظر شما چیست؟

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