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

افرادی که در رقابت‌های برنامه‌نویسی شرکت می‌کنند می‌دانند که اعداد اول، از جمله موضوعات کلیدی است که طراحان سوال به آن می‌پردازند و سوالاتی پیرامون اعداد اول طرح می‌کنند. این در حالی است که دانشجویان رشته‌های علوم و مهندسی کامپیوتر نیز در دروسی مانند مبانی برنامه‌نویسی، ساختمان داده‌ها و طراحی الگوریتم با مسائل متعدد مربوط به اعداد اول آشنا می‌شوند. در این مطلب، چندین الگوریتم تشخیص عدد اول معرفی و در «زبان برنامه‌نویسی پایتون» (Python Programming Language) پیاده‌سازی می‌شوند. در واقع، چگونگی بهینه‌سازی تابع برای تعیین اعداد اول در یک دامنه داده شده تشریح می‌شود و سپس، زمان اجرای روش‌های بهینه بیان شده محاسبه می‌شوند. پیش از این نیز در مطلبی با عنوان «برنامه تشخیص اعداد اول در پایتون — به زبان ساده» به الگوریتم تشخیص اعداد اول پرداخته شده بود.

بر اساس تعریف، عدد اول یک عدد صحیح مثبت است که تنها بر خودش و ۱ تقسیم‌پذیر است. برای مثال، ۲، ۳، ۳، ۵ و ۷ اعداد اول هستند. اما، اگر یک عدد را بتوان به اعداد کوچک‌تر از خودش تجزیه کرد، به آن «عدد مرکب» (Composite Number) گفته می‌شود. برای مثال، 4=2*2، 6=2*3. عدد صحیح و مثبت هستند و عدد ۱ نه عدد اول است و نه مرکب است. بررسی اینکه آیا یک عدد اول است یا خیر در حالت کلی آسان است، اما انجام این کار به صورت بهینه و کارا، نیاز به تلاش بیشتری دارد.

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

در اینجا، از یک تابع خیلی ابتدایی برای بررسی اینکه یک عدد، برای مثال n، اول است یا نه استفاده می‌شود. در این روش، همه مقسوم‌علیه‌ها از ۲ تا n-1 مورد بررسی قرار می‌گیرد. از ۱ و خود n صرف‌نظر می‌شود. اگر n بر هر عددی بخش‌پذیر بود، تابع مقدار False را باز می‌گرداند و در غیر این صورت، مقدار True را باز می‌گرداند. در ادامه، گام‌های مورد استفاده در این روش ارائه شده‌اند.

1. اگر عدد صحیح، کمتر یا مساوی ۱ باشد، مقدار False را بازگردان.
2. اگر یک عدد داده شده بر هر عددی از ۲ تا n بخش‌پذیر باشد، مقدار False را بازگردان.
3. در غیر این صورت، مقدار True را بازگردان.

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

1# Python Program to find prime numbers in a range 
2import time 
3def is_prime(n): 
4    if n <= 1: 
5        return False
6    for i in range(2,n): 
7        if n % i == 0: 
8            return False
9    return True
10  
11# Driver function 
12t0 = time.time() 
13c = 0 #for counting 
14  
15for n in range(1,100000): 
16    x = is_prime(n) 
17    c += x 
18print("Total prime numbers in range :", c) 
19  
20t1 = time.time() 
21print("Time required :", t1 - t0)

خروجی:

Total prime numbers in range: 9592
Time required: 60.702312707901

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

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

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

فیلم آموزش مبانی برنامه نویسی – الگوریتم و فلوچارت با رویکرد حل مساله در فرادرس

کلیک کنید

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

36=1*36 
=2*18
=3*12
=4*9
------------
=6*6
------------
=9*4
=12*3
=18*2
=36*1

در این تابع، یک عدد صحیح که max_div نامیده شده محاسبه می‌شود؛ این عدد، ریشه دوم عدد است و مقدار جز صحیح با استفاده از کتابخانه پایتون math محاسبه می‌شود. در مثال پیشین، از ۲ تا n-1 تکرار انجام می‌شد. اما در اینجا، مقسوم‌علیه‌ها به نیمی کاهش پیدا می‌کنند. نیاز به «وارد» (import) کردن ماژول math برای استفاده از توابع floor و sqrt است. گام‌های زیر، در این روش مورد استفاده قرار می‌گیرند.

1. اگر عدد صحیح، کمتر یا مساوی با ۱ است، مقدار False را بازگردان.
2. اکنون، تعداد ارقامی که بخش‌پذیری n بر آن‌ها مورد بررسی قرار می‌گیرد را به تعداد ریشه دوم عدد کاهش بده.
3. اگر عدد قابل تقسیم به هر عددی از n تا ریشه دوم عدد بود، مقدار false را باز گردان.
4. در غیر این صورت، مقدار true را بازگردان.

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

1# Python Program to find prime numbers in a range 
2import math 
3import time 
4def is_prime(n): 
5    if n <= 1: 
6        return False
7  
8    max_div = math.floor(math.sqrt(n)) 
9    for i in range(2, 1 + max_div): 
10        if n % i == 0: 
11            return False
12    return True
13  
14# Driver function 
15t0 = time.time() 
16c = 0 #for counting 
17  
18for n in range(1,100000): 
19    x = is_prime(n) 
20    c += x 
21print("Total prime numbers in range :", c) 
22  
23t1 = time.time() 
24print("Time required :", t1 - t0)

خروجی:

Total prime numbers in range: 9592
Time required: 0.4116342067718506

در کد بالا، تعداد اعداد از ۱ تا ۱۰۰۰۰۰ از جهت اول بودن بررسی می‌شوند. این کار، نسبت به روش قبلی، زمان نسبتا کمتری می‌برد. در این رویکرد، ترفند کوچکی زده شده، اما زمان اجرا به میزان قابل توجهی تغییر می‌کند. بنابراین، نسبت به روش قبلی، ترجیح داده می‌شود.

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

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

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

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

1. اگر عدد صحیح، کمتر یا مساوی یک بود، مقدار False را بازگردان.
2. اگر عدد برابر با ۲ بود، مقدار True را بازگردان.
3. اگر عدد بزرگ‌تر از ۲ و بخش‌پذیر بر ۲ بود، مقدار false را بازگردان.
4. اکنون، همه اعداد فرد مورد بررسی قرار می‌گیرند.
5. اگر عدد داده شده بر اعداد از ۳ تا ریشه دوم خودش بخش‌پذیر است (صرف‌نظر از مقادیر زوج)، مقدار false را باز گردان.
6. در غیر این صورت، مقدار true را بازگردان.

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

1# Python Program to find prime numbers in a range 
2import math 
3import time 
4def is_prime(n): 
5    if n <= 1: 
6        return False
7    if n == 2: 
8        return True
9    if n > 2 and n % 2 == 0: 
10        return False
11  
12    max_div = math.floor(math.sqrt(n)) 
13    for i in range(3, 1 + max_div, 2): 
14        if n % i == 0: 
15            return False
16    return True
17  
18# Driver function 
19t0 = time.time() 
20c = 0 #for counting 
21  
22for n in range(1,100000): 
23    x = is_prime(n) 
24    c += x 
25print("Total prime numbers in range :", c) 
26  
27t1 = time.time() 
28print("Time required :", t1 - t0)

خروجی:

Total prime numbers in range: 9592
Time required: 0.23305177688598633

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

روش غربال

این روش، همه اعداد اول کوچک‌تر و مساوی یک عدد داده شده n را محاسبه می‌کند. برای مثال، اگر n برابر با ۱۰ باشد، خروجی باید ۲، ۳، ۵، ۷ باشد. اگر n برابر با ۲۰ باشد، خروجی باید {19 ,17 ,13 ,11 ,7 ,5 ,3 ,2} باشد. این روش، کارآمدترین و سریع‌ترین روش برای محاسبه همه اعداد اول پیش از یک عدد داده شده است. این الگوریتم تشخیص عدد اول، برای بررسی یک عدد خاص مناسب نیست. بلکه، برای تولید لیستی از اعداد اول مناسب است.

فیلم آموزش تابع در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

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

1# Python Program to find prime numbers in a range 
2import time 
3def SieveOfEratosthenes(n): 
4       
5    # Create a boolean array "prime[0..n]" and  
6    # initialize all entries it as true. A value  
7    # in prime[i] will finally be false if i is 
8    # Not a prime, else true. 
9    prime = [True for i in range(n+1)] 
10      
11    p = 2
12    while(p * p <= n): 
13           
14        # If prime[p] is not changed, then it is  
15       # a prime 
16        if (prime[p] == True): 
17               
18            # Update all multiples of p 
19            for i in range(p * 2, n + 1, p): 
20                prime[i] = False
21        p += 1
22    c = 0
23  
24    # Print all prime numbers 
25    for p in range(2, n): 
26        if prime[p]: 
27            c += 1
28    return c 
29  
30# Driver function 
31t0 = time.time() 
32c = SieveOfEratosthenes(100000) 
33print("Total prime numbers in range:", c) 
34  
35t1 = time.time() 
36print("Time required:", t1 - t0)

خروجی:

Total prime numbers in range: 9592
Time required: 0.0312497615814209

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

فیلم مجموعه آموزش برنامه نویسی – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

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

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• برنامه تشخیص اعداد اول در پایتون — به زبان ساده
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^