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

فرض کنید عدد اول است و مقسوم‌علیه‌ها را از ۲ تا جذر n امتحان کنید. اگر یکی از آن‌ها عدد را بدون باقی‌مانده تقسیم کرد، فرضتان غلط بوده است.

n = int(input())

is_prime = n >= 2
for d in range(2, int(n ** 0.5) + 1):
    if n % d == 0:
        is_prime = False
        break

if is_prime:
    print("اول است")
else:
    print("اول نیست")

این جواب چطور کار می‌کند؟

متغیر is_prime از اول با n >= 2 مقدار می‌گیرد. همین یک سطر حالت‌های ۰ و ۱ را کنار می‌گذارد، چون برای آن‌ها مقدار اولیه False است و حلقه هم چیزی را عوض نمی‌کند.

اگر n بر عددی بزرگ‌تر از جذرش بخش‌پذیر باشد، خارج‌قسمت آن تقسیم از جذر کوچک‌تر است و حلقه آن را زودتر پیدا کرده است. به همین دلیل امتحان تا int(n ** 0.5) کافی است و برای عددهای بزرگ برنامه را خیلی سریع‌تر می‌کند.

شرط n % d == 0 یعنی تقسیم باقی‌مانده ندارد. با پیدا شدن اولین مقسوم‌علیه، break حلقه را تمام می‌کند، چون جواب دیگر عوض نمی‌شود. برای ۲ و ۳ بازهٔ حلقه خالی است و جواب همان مقدار اولیه می‌ماند.

راه دوم: ساختار for-else

n = int(input())

if n < 2:
    print("اول نیست")
else:
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            print("اول نیست")
            break
    else:
        print("اول است")

بخش else یک حلقهٔ for فقط وقتی اجرا می‌شود که حلقه بدون break تمام شده باشد. این ساختار مخصوص پایتون است و متغیر پرچم را لازم نمی‌کند. برای عددهای خیلی بزرگ، math.isqrt(n) جذر صحیح را دقیق‌تر از n ** 0.5 می‌دهد.