تشخیص عدد اول و زوج یا فرد در پایتون؛ ۵ روش از ساده تا سریع
🗓 آخرین به‌روزرسانی:
تشخیص عدد اول و تشخیص زوج یا فرد بودن عدد، دو تمرین کلاسیک برای شروع برنامه‌نویسی پایتون هستند. این تمرین‌ها ساده به نظر می‌رسند، اما یاد می‌دهند چطور شرط، حلقه، تابع و حتی بهینه‌سازی الگوریتم را کنار هم بگذارید. در این آموزش اول زوج و فرد را حل میکنیم، بعد پنج روش تشخیص عدد اول را از ساده‌ترین تا سریعترین می‌نویسیم و سرعتشان را واقعاً اندازه می‌گیریم.
همه نمونه‌کدها با پایتون 3.13.5 اجرا شده‌اند و خروجی زیر هر کد، خروجی واقعی همان اجراست.
بخش اول: تشخیص زوج یا فرد در پایتون
عدد زوج عددی است که بر ۲ بخش‌پذیر باشد؛ یعنی باقی‌مانده تقسیم آن بر ۲ صفر شود. در پایتون باقی‌مانده با عملگر % محاسبه میشود. اگر با این عملگر آشنا نیستید، آموزش عملگرهای حسابی و مقایسه‌ای را ببینید.
روش اول: عملگر باقی‌مانده
def even_or_odd(n):
if n % 2 == 0:
return "even"
return "odd"
for n in [4, 7, 0, -3, 10]:
print(n, even_or_odd(n))خروجی:
4 even
7 odd
0 even
-3 odd
10 evenدقت کنید که در پایتون حاصل -3 % 2 برابر ۱ است، نه منفی ۱. برای همین همین تابع برای عددهای منفی هم درست کار میکند؛ نکته‌ای که در بعضی زبان‌های دیگر صادق نیست.
روش دوم: بیت آخر عدد
در مبنای دو، بیت آخر هر عدد فرد برابر ۱ است. عملگر & (AND بیتی) این بیت را جدا میکند. این روش بیشتر جنبه آموزشی دارد و در پایتون تفاوت سرعت محسوسی با % ایجاد نمی‌کند:
for n in [4, 7, 15, 22]:
print(n, "odd" if n & 1 else "even", bin(n))خروجی:
4 even 0b100
7 odd 0b111
15 odd 0b1111
22 even 0b10110گرفتن عدد از کاربر
برنامه کامل با گرفتن ورودی و مدیریت ورودی نادرست به این شکل است. در خروجی زیر، ورودی «abc» داده شده تا رفتار برنامه در برابر خطا را ببینید:
text = input("Enter a number: ")
try:
n = int(text)
print(n, "is", "even" if n % 2 == 0 else "odd")
except ValueError:
print("Please enter a whole number.")خروجی:
Enter a number: abc
Please enter a whole number.اگر try نبود، برنامه با خطای ValueError متوقف می‌شد. برای آشنایی بیشتر آموزش مدیریت خطا در پایتون را بخوانید.
بخش دوم: عدد اول چیست؟
عدد اول عدد طبیعی بزرگتر از ۱ است که فقط بر ۱ و خودش بخش‌پذیر باشد. ۲، ۳، ۵، ۷، ۱۱ و ۱۳ اول هستند؛ ۱ اول نیست و ۲ تنها عدد اول زوج است. بنابراین هر تابع تشخیص عدد اول باید این سه نکته را رعایت کند: عددهای کوچکتر از ۲ اول نیستند، ۲ اول است و هیچ عدد زوج دیگری اول نیست.
روش ۱: بررسی همه مقسوم‌علیه‌ها (ساده‌ترین)
ساده‌ترین ایده این است که همه عددهای ۲ تا n−1 را امتحان کنیم. اگر هیچ‌کدام n را نشمارد، n اول است:
def is_prime_simple(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return True
print([n for n in range(1, 30) if is_prime_simple(n)])خروجی:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]این روش درست است اما برای عددهای بزرگ کند است؛ برای یک عدد اول هفت‌رقمی تقریباً یک میلیون تقسیم انجام می‌دهد. در عبارت آخر از list comprehension استفاده شده است.
روش ۲: بررسی تا جذر عدد
اگر n = a × b باشد، حتماً یکی از a یا b کوچکتر یا مساوی جذر n است. پس کافی است فقط تا جذر را بررسی کنیم. تابع math.isqrt جذر صحیح را بدون خطای اعشاری برمی‌گرداند:
from math import isqrt
def is_prime_sqrt(n):
if n < 2:
return False
for d in range(2, isqrt(n) + 1):
if n % d == 0:
return False
return True
for n in [1, 2, 9, 97, 1_000_003]:
print(n, is_prime_sqrt(n))خروجی:
1 False
2 True
9 False
97 True
1000003 Trueبا این تغییر کوچک، برای عدد ۱٬۰۰۰٬۰۰۳ به‌جای حدود یک میلیون تقسیم، فقط حدود هزار تقسیم انجام میشود. این همان روشی است که در مصاحبه‌های برنامه‌نویسی انتظار دارند بلد باشید.
روش ۳: حذف زوج‌ها و الگوی 6k±1
همه عددهای اول بزرگتر از ۳ به شکل 6k−1 یا 6k+1 هستند، چون بقیه حالت‌ها بر ۲ یا ۳ بخش‌پذیرند. پس بعد از بررسی ۲ و ۳ می‌توانیم با گام ۶ جلو برویم و در هر مرحله فقط دو عدد را امتحان کنیم:
def is_prime_6k(n):
if n < 2:
return False
if n < 4:
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 += 6
return True
print([n for n in range(1, 50) if is_prime_6k(n)])خروجی:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]در اینجا از حلقه while استفاده شده چون گام حلقه ثابت نیست و شرط توقف به i * i وابسته است.
روش ۴: نسخه کوتاه با all
تابع داخلی all وقتی True برمی‌گرداند که همه مقدارهای داده‌شده درست باشند و به محض دیدن اولین False متوقف میشود. با آن می‌توانیم روش ۲ را در یک خط بنویسیم:
from math import isqrt
def is_prime_all(n):
return n > 1 and all(n % d for d in range(2, isqrt(n) + 1))
print([is_prime_all(n) for n in (0, 1, 2, 15, 17)])خروجی:
[False, False, True, False, True]این نسخه خوانا و کوتاه است، اما برای مبتدی‌ها روش ۲ قابل‌فهم‌تر است. هر دو از نظر تعداد تقسیم یکسان‌اند.
روش ۵: غربال اراتستن برای پیدا کردن همه اعداد اول تا N
وقتی به‌جای یک عدد، همه عددهای اول تا N را لازم دارید، غربال اراتستن بسیار سریع‌تر است. ایده: فهرستی از True می‌سازیم و از ۲ شروع میکنیم؛ مضرب‌های هر عدد اول را False میکنیم. آنچه باقی می‌ماند، اول است:
def sieve(limit):
is_p = [True] * (limit + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(limit ** 0.5) + 1):
if is_p[i]:
for j in range(i * i, limit + 1, i):
is_p[j] = False
return [i for i, ok in enumerate(is_p) if ok]
primes = sieve(100)
print(primes)
print("count:", len(primes))خروجی:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
count: 25مقایسه سرعت روش‌ها
حرف زدن درباره سرعت بدون اندازه‌گیری فایده ندارد. کد زیر با ماژول time زمان پیدا کردن همه عددهای اول زیر ۲۰٬۰۰۰ را برای هر روش اندازه می‌گیرد. عددهای دقیق روی هر کامپیوتر متفاوت است، اما نسبت‌ها مشابه می‌ماند:
import time
from math import isqrt
def simple(n):
return n > 1 and all(n % d for d in range(2, n))
def to_sqrt(n):
return n > 1 and all(n % d for d in range(2, isqrt(n) + 1))
def sieve(limit):
p = [True] * (limit + 1); p[0] = p[1] = False
for i in range(2, isqrt(limit) + 1):
if p[i]:
p[i*i::i] = [False] * len(p[i*i::i])
return [i for i, ok in enumerate(p) if ok]
N = 20_000
for name, fn in [("simple", lambda: [n for n in range(N) if simple(n)]),
("sqrt", lambda: [n for n in range(N) if to_sqrt(n)]),
("sieve", lambda: sieve(N - 1))]:
t = time.perf_counter(); r = fn(); dt = time.perf_counter() - t
print(f"{name:7} found={len(r)} time={dt*1000:.1f} ms")خروجی:
simple found=2262 time=784.5 ms
sqrt found=2262 time=12.3 ms
sieve found=2262 time=0.9 msهر سه روش تعداد یکسانی عدد اول پیدا می‌کنند، اما روش ساده چندین برابر کندتر است و غربال از همه سریع‌تر. نتیجه عملی: برای تست یک عدد از روش جذر یا 6k±1 و برای تولید فهرست از غربال استفاده کنید.
عدد اول در دنیای واقعی کجا به کار می‌رود؟
شاید فکر کنید عدد اول فقط یک تمرین کلاسی است، اما این مفهوم در پشت بسیاری از فناوری‌های روزمره قرار دارد. امنیت اتصال HTTPS که هنگام خرید اینترنتی از آن استفاده می‌کنید، در بخشی از الگوریتم‌هایش به دشواری تجزیه حاصل‌ضرب دو عدد اول بسیار بزرگ وابسته است. جدول‌های درهم‌سازی (Hash Table) که دیکشنری پایتون هم بر پایه همین ایده کار میکند، در بعضی پیاده‌سازی‌ها از اندازه‌های اول برای پخش بهتر داده‌ها بهره می‌برند. تولیدکننده‌های عدد شبه‌تصادفی هم گاهی از پیمانه‌های اول استفاده می‌کنند.
از نگاه یادگیری، ارزش این تمرین در خود الگوریتم است: شما یاد می‌گیرید یک راه‌حل درست اما کند را قدم‌به‌قدم سریع کنید، فرضیه‌تان را با اندازه‌گیری بسنجید و درستی نسخه بهینه را با تست ثابت کنید. این سه مهارت، یعنی بهینه‌سازی، اندازه‌گیری و تست، همان چیزی است که برنامه‌نویس حرفه‌ای را از مبتدی جدا میکند و در هر پروژه‌ای به کارتان می‌آید.
تمرین‌های پیشنهادی
- برنامه‌ای بنویسید که عدد را از کاربر بگیرد و هم زوج/فرد بودن و هم اول بودن آن را چاپ کند.
- تابعی بنویسید که n-امین عدد اول را برگرداند (مثلاً دهمین عدد اول ۲۹ است).
- عددهای اول دوقلو (مثل ۱۱ و ۱۳) زیر ۱۰۰ را پیدا کنید.
- یک عدد را به عامل‌های اول تجزیه کنید؛ مثلاً ۸۴ = ۲ × ۲ × ۳ × ۷.
جواب تمرین دوم برای مقایسه با کد خودتان:
from math import isqrt
def is_prime(n):
return n > 1 and all(n % d for d in range(2, isqrt(n) + 1))
def nth_prime(k):
count, n = 0, 1
while count < k:
n += 1
if is_prime(n):
count += 1
return n
print(nth_prime(10), nth_prime(100))خروجی:
29 541برای تمرین‌های بیشتر از این دست، سراغ کدهای آماده پایتون و پروژه‌هایی مثل بازی حدس عدد بروید.
تجزیه عدد به عامل‌های اول
یکی از کاربردهای مستقیم ایده «تا جذر» تجزیه عدد به عامل‌های اول است. در این روش از کوچک‌ترین مقسومعلیه شروع میکنیم و تا وقتی عدد بر آن بخش‌پذیر است تقسیمش میکنیم. اگر در پایان چیزی بزرگتر از ۱ باقی ماند، خودش یک عامل اول است. این همان جواب تمرین چهارم است، پس اگر می‌خواهید خودتان حلش کنید، اول کد خودتان را بنویسید:
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
for n in [84, 97, 360, 1001]:
print(n, "=", " x ".join(map(str, prime_factors(n))))خروجی:
84 = 2 x 2 x 3 x 7
97 = 97
360 = 2 x 2 x 2 x 3 x 3 x 5
1001 = 7 x 11 x 13عملگر //= تقسیم صحیح را انجام می‌دهد و حاصل را در همان متغیر می‌ریزد. چون عدد در هر مرحله کوچکتر میشود، شرط حلقه بیرونی هم زودتر برقرار نمی‌ماند و الگوریتم سریع تمام میشود. خروجی ۹۷ فقط خود ۹۷ است؛ یعنی این تابع به‌طور غیرمستقیم اول بودن را هم نشان می‌دهد.
آزمودن تابع با assert
وقتی چند نسخه از یک تابع دارید، بهترین راه اطمینان از درستی آن‌ها مقایسه نتیجه‌شان با هم است. دستور assert اگر شرط نادرست باشد خطا می‌دهد و اگر درست باشد بی‌صدا رد میشود. کد زیر سه روش را روی همه عددهای ۰ تا ۵۰۰۰ مقایسه میکند:
from math import isqrt
def a(n):
return n > 1 and all(n % d for d in range(2, n))
def b(n):
return n > 1 and all(n % d for d in range(2, isqrt(n) + 1))
def c(n):
if n < 4:
return n > 1
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 += 6
return True
for n in range(5000):
assert a(n) == b(n) == c(n), n
print("all three methods agree for 0..4999")خروجی:
all three methods agree for 0..4999این عادت ساده، یعنی نوشتن تست کوچک برای کد خودتان، در پروژه‌های واقعی جلوی بسیاری از باگ‌ها را می‌گیرد. هر بار که الگوریتمی را بهینه می‌کنید، نسخه ساده و مطمئن قبلی را نگه دارید و خروجی نسخه جدید را با آن مقایسه کنید.
برای عددهای خیلی بزرگ چه کنیم؟
روش‌های این آموزش برای عددهایی تا ده‌ها یا صدها میلیارد هم در زمان معقول جواب می‌دهند، چون تعداد تقسیم‌ها با جذر عدد رشد میکند. اما در رمزنگاری با عددهایی صدها رقمی سروکار داریم که جذرشان هم بسیار بزرگ است. در این حالت از آزمون‌های احتمالاتی مثل میلر-رابین استفاده میشود که به‌جای تقسیم، با توان‌رسانی پیمانه‌ای کار می‌کنند. تابع داخلی pow(a, b, m) پایتون این توان‌رسانی را سریع انجام می‌دهد. یادگیری این آزمون برای سطح متوسط به بعد پیشنهاد میشود و برای تمرین‌های دانشگاهی و مصاحبه‌ای معمولاً همان روش جذر کافی است.
اشتباه‌های رایج
- اول دانستن عدد ۱؛ شرط
n < 2را فراموش نکنید. - استفاده از
n ** 0.5بدون+ 1در range؛ در این صورت مثلاً ۲۵ اشتباهاً اول تشخیص داده میشود. - چاپ پیام داخل حلقه به‌جای برگرداندن نتیجه؛ تابع خوب مقدار True یا False برمی‌گرداند و چاپ را به بیرون می‌سپارد.
- مقایسه رشته با عدد؛ ورودی
inputرشته است و باید باintتبدیل شود، وگرنه خطای TypeError می‌گیرید.
📌 همچنین بخوانید: تمرین پایتون با جواب، ساخت بازی با پایتون و Pygame و ساخت ربات با پایتون
سوالات متداول
سریعترین روش تشخیص عدد اول در پایتون چیست؟
برای یک عدد معمولی، بررسی تا جذر یا الگوی 6k±1 کافی و سریع است. برای تولید همه اعداد اول تا N، غربال اراتستن سریعترین روش ساده است.
آیا ۱ عدد اول است؟
خیر. طبق تعریف، عدد اول باید بزرگتر از ۱ باشد و دقیقاً دو مقسومعلیه داشته باشد.
چطور زوج یا فرد بودن عدد را در پایتون بفهمیم؟
از n % 2 استفاده کنید؛ اگر صفر بود عدد زوج و اگر ۱ بود فرد است. این روش برای عددهای منفی هم در پایتون درست کار میکند.
چرا فقط تا جذر عدد بررسی میکنیم؟
چون اگر عددی مقسومعلیه بزرگتر از جذرش داشته باشد، حتماً مقسومعلیه متناظر کوچکتر از جذر هم دارد که زودتر پیدا میشود.