الگوریتم‌های اعداد
الگوریتم‌های اعداد: آزمون اول بودن بهینه، سیو اراتوستن برای همه اعداد اول و الگوریتم اقلیدس GCD
سه الگوریتم پایه اعداد
این سه الگوریتم در مسائل الگوریتمی و برنامه‌نویسی واقعی مدام برمی‌گردند:
۱. اول بودن — فقط تا جذر!
اگر n مرکب باشد، حتماً عاملی ≤ √n دارد (اگر همه عامل‌ها بزرگ‌تر از جذر بودند، حاصل‌ضرب از n بزرگ‌تر می‌شد!). پس فقط تا جذر بررسی کنید — O(√n) به‌جای O(n).
بهینه‌تر: فقط ۲ و اعداد فرد — نصفِ عملیات!
۲. سیو اراتوستن (Sieve of Eratosthenes)
«همه اعداد اول تا n» لازم است؟ سیو: همه را اول علامت بزن؛ از ۲ شروع، مضارب هر اول را «مرکب» علامت بزن. فقط از i² شروع کن (کوچک‌ترها قبلاً زده شده‌اند)!
- پیچیدگی: O(n log log n) — تقریباً خطی!
- حافظه: O(n) — برای n تا ~۱۰ میلیون عالی
۳. الگوریتم اقلیدس GCD
بزرگ‌ترین مقسوم‌علیه مشترک — زیبایی ریاضی:
gcd(a, b) = gcd(b, a mod b)
gcd(a, 0) = aمثال: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6
هر دو گام حداقل نصف می‌شوند ← O(log min(a,b))!
کاربردها
| الگوریتم | کاربرد |
|---|---|
| اول بودن | رمزنگاری، مسائل اعداد |
| سیو | پیش‌محاسبه اول‌ها، فاکتورگیری |
| GCD | کسر به فرم کوچک، LCM، زمان‌بندی تناوبی |
LCM: کوچک‌ترین مضرب مشترک = a×b / gcd(a,b) — برای «چند بار بعد هم‌زمان می‌شوند؟»
جمع‌بندی
- اول بودن: فقط تا جذر + فقط فرد‌ها — O(√n)
- سیو اراتوستن: همه اول‌ها تا n در O(n log log n)
- اقلیدس: gcd با mod — O(log)
- LCM از gcd: a×b/gcd
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.