کنترل جریان

تمرین حلقه: عدد اول، جمع اعداد اول و فاکتوریل

۵ دقیقه مطالعه · به‌روزرسانی ۲۲ مهر ۱۴۰۵

با شرط، while و for حالا می‌شود مسئله‌های واقعی حل کرد. در این درس چند مسئلهٔ کلاسیک را قدم به قدم حل می‌کنیم. هدف فقط جواب نیست؛ ببینید یک راه‌حل چطور از «کار می‌کند» به «خوب کار می‌کند» می‌رسد.

۱. آیا عدد اول است؟

عدد اول عددی بزرگ‌تر از ۱ است که فقط بر ۱ و خودش بخش‌پذیر باشد: ۲، ۳، ۵، ۷، ۱۱، …

نسخهٔ ۱: شمردن همهٔ مقسوم‌علیه‌ها

ساده‌ترین فکر: همهٔ اعداد ۲ تا n-1 را امتحان کن و بشمار چندتایشان n را می‌شمارند. اگر هیچ‌کدام نشمردند، اول است.

n = int(input("Enter a number: "))

divisors = 0
for i in range(2, n):
    if n % i == 0:
        divisors += 1

if divisors == 0:
    print("اول است")
else:
    print("اول نیست")

درست کار می‌کند، ولی بی‌دلیل زیاد کار می‌کند: برای ۱۰۰۰ همهٔ ۹۹۸ عدد را امتحان می‌کند، در حالی که از همان اول (۲) معلوم بود اول نیست.

نسخهٔ ۲: پرچم (flag)

لازم نیست تعداد مقسوم‌علیه‌ها را بدانیم؛ فقط می‌خواهیم بدانیم حداقل یکی هست یا نه. یک متغیر بولی به‌عنوان «پرچم» نگه می‌داریم:

n = int(input("Enter a number: "))

is_prime = True
for i in range(2, n):
    if n % i == 0:
        is_prime = False

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

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

نسخهٔ ۳: break

به محض اینکه یک مقسوم‌علیه پیدا شد، جواب معلوم است؛ break می‌کنیم:

n = int(input("Enter a number: "))

is_prime = True
for i in range(2, n):
    if n % i == 0:
        is_prime = False
        break

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

حالا برای ۱۰۰۰ فقط یک دور اجرا می‌شود.

نسخهٔ ۴ (اضافه): تا جذر کافی است

اگر n = a × b باشد، یکی از a یا b حتماً کوچک‌تر یا مساوی √n است. پس اگر تا √n مقسوم‌علیهی پیدا نشد، بعدش هم پیدا نمی‌شود:

n = 1_000_003

is_prime = n > 1
i = 2
while i * i <= n:
    if n % i == 0:
        is_prime = False
        break
    i += 1

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

برای یک عدد اول حدود یک میلیون، نسخهٔ ۳ حدود یک میلیون دور می‌زند و این نسخه فقط حدود هزار دور. همان جواب، هزار برابر سریع‌تر.

💡 نسخه‌های ۱ تا ۳ برای n = 1 و n = 0 جواب غلط «اول است» می‌دهند (حلقه اصلاً اجرا نمی‌شود). در نسخهٔ ۴ با is_prime = n > 1 این حالت را درست کردیم. همیشه کدتان را با ورودی‌های مرزی (۰، ۱، منفی، خیلی بزرگ) تست کنید.

۲. همهٔ اعداد اول تا n، و جمعشان

حالا باید تشخیص اول بودن را برای هر عدد از ۲ تا n تکرار کنیم: یک حلقه داخل یک حلقهٔ دیگر.

n = int(input("ye adad vared kon: "))

total = 0
for i in range(2, n + 1):          # حلقهٔ بیرونی: هر عدد
    is_prime = True
    for j in range(2, i):          # حلقهٔ درونی: بررسی اول بودن i
        if i % j == 0:
            is_prime = False
            break
    if is_prime:
        total += i
        print(f"{i} is a prime number")

print(f"the sum of all prime numbers from 2 to {n} is {total}")

نکته‌های کلیدی:

• is_prime = True داخل حلقهٔ بیرونی است تا برای هر عدد از نو شروع شود. اگر بیرون می‌گذاشتیم، بعد از اولین عدد غیراول، برای همیشه False می‌ماند. (این باگ را حتماً یک بار امتحان کنید!)
• break فقط از حلقهٔ درونی خارج می‌شود؛ حلقهٔ بیرونی سراغ عدد بعدی می‌رود.
• اسم متغیر جمع را sum نگذاشتیم، چون sum نام یک تابع داخلی پایتون است (چرا مهم است؟).

💡 وقتی به توابع برسیم، تشخیص اول بودن را در یک تابع is_prime(n) می‌گذاریم و این کد خیلی خواناتر می‌شود.

۳. فاکتوریل (سؤال پرتکرار)

فاکتوریل k یعنی حاصل‌ضرب ۱ تا k: 5! = 1 × 2 × 3 × 4 × 5 = 120، و طبق تعریف 0! = 1.

این همان الگوی جمع‌زدن است، فقط با ضرب. پس مقدار اولیه باید ۱ باشد، نه ۰ (چرا؟):

k = int(input("k: "))

fact = 1
for i in range(2, k + 1):
    fact *= i

print(f"{k}! = {fact}")

با k = 100 امتحان کنید! پایتون اعداد صحیح را با هر اندازه‌ای پشتیبانی می‌کند (برخلاف خیلی از زبان‌ها که سرریز می‌شوند).

تمرین

۱. تکرار حروف (نسخهٔ کلی)

رشته‌ای بگیرید و هر حرفش را سه بار تکرار کنید: MCI ← MMMCCCIII، salam ← sssaaalllaaammm.

text = input("متن: ")
result = ""
for ch in text:
    result += ch * 3
print(result)

۲. مقسوم‌علیه‌ها

عددی بگیرید و همهٔ مقسوم‌علیه‌هایش را در یک خط چاپ کنید. مثلاً برای ۱۲: 1 2 3 4 6 12.

n = int(input("n: "))
for i in range(1, n + 1):
    if n % i == 0:
        print(i, end=" ")

۳. عدد کامل

عددی «کامل» است که با جمع مقسوم‌علیه‌هایش (به‌جز خودش) برابر باشد؛ مثل 6 = 1 + 2 + 3. همهٔ اعداد کامل کوچک‌تر از ۱۰۰۰ را پیدا کنید.

for n in range(2, 1000):
    total = 0
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            total += i
    if total == n:
        print(n)