غربال اراتستن
Sieve of Eratosthenesغربال اراتستن همه اعداد اول تا n را با علامت‌زدن مضرب‌های اعداد اول به‌عنوان composite پیدا می‌کند.
اول این مفهوم را در ذهن نگه دار
غربال اراتستن همه اعداد اول تا n را با علامت‌زدن مضرب‌های اعداد اول به‌عنوان composite پیدا می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
ابتدا همه اعداد کاندید اول بودن هستند.
برای هر p اول تا √n، مضرب‌ها را از p² علامت بزن؛ مضرب‌های کوچک‌تر قبلاً توسط primeهای کوچک‌تر پوشش داده شده‌اند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
خاصیت یا رابطه ریاضی را واضح بگو.
محدوده اعداد و representation را مشخص کن.
رابطه را به computation تبدیل و precision/overflow را بررسی کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای غربال اراتستن هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
function primesUpTo(n) {
const prime = Array(n + 1).fill(true);
prime[0] = prime[1] = false;
for (let p = 2; p * p <= n; p++) {
if (!prime[p]) continue;
for (let x = p * p; x <= n; x += p) prime[x] = false;
}
return prime.flatMap((isPrime, i) => isPrime ? [i] : []);
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
O(n log log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی خاصیت ریاضی می‌تواند brute force را حذف کند از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن precision ممیز شناور یا دامنه integer.
- استفاده از فرمول خارج از فرض‌های معتبرش.
مدل یک پاسخ حرفه‌ای
O(n log log n) زمان و O(n) حافظه را بگو و دلیل شروع از p² را توضیح بده.
غربال اراتستن چه مسئله‌ای را حل می‌کند؟
غربال اراتستن همه اعداد اول تا n را با علامت‌زدن مضرب‌های اعداد اول به‌عنوان composite پیدا می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(n log log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن precision ممیز شناور یا دامنه integer.