پرش به محتویات

غربال خطی

با داشتن عدد $n$، تمام اعداد اول در بازهٔ $[2, n]$ را پیدا کنید.

روش استاندارد برای حل این مسئله، استفاده از غربال اراتستن است. این الگوریتم بسیار ساده است، اما زمان اجرای آن $O(n \log \log n)$ است.

اگرچه الگوریتم‌های شناخته‌شدهٔ زیادی با زمان اجرای زیرخطی (یعنی $o(n)$) وجود دارند، الگوریتمی که در ادامه توضیح داده می‌شود به دلیل سادگی‌اش جالب است: این الگوریتم از غربال کلاسیک اراتستن پیچیده‌تر نیست.

علاوه بر این، الگوریتم ارائه‌شده در اینجا به عنوان یک محصول جانبی، تجزیه به عوامل اول تمام اعداد در بازهٔ $[2, n]$ را محاسبه می‌کند و این می‌تواند در بسیاری از کاربردهای عملی مفید باشد.

نقطه ضعف این الگوریتم، استفاده از حافظهٔ بیشتر نسبت به غربال کلاسیک اراتستن است: این الگوریتم به آرایه‌ای از $n$ عدد نیاز دارد، در حالی که برای غربال کلاسیک اراتستن داشتن $n$ بیت حافظه (که ۳۲ برابر کمتر است) کافی است.

بنابراین، استفاده از الگوریتم توصیف‌شده فقط برای اعداد تا مرتبهٔ $10^7$ و نه بیشتر منطقی است.

این الگوریتم توسط پل پریچارد (Paul Pritchard) ارائه شده است. این یک نسخه از الگوریتم ۳.۳ در (Pritchard, 1987: به مراجع در انتهای مقاله مراجعه کنید) است.

الگوریتم

هدف ما محاسبهٔ کوچکترین عامل اول ($lp [i]$) برای هر عدد $i$ در بازهٔ $[2, n]$ است.

علاوه بر این، باید لیستی از تمام اعداد اول پیدا شده را ذخیره کنیم - بیایید آن را $pr []$ بنامیم.

مقادیر $lp [i]$ را با صفر مقداردهی اولیه می‌کنیم، که به این معنی است که فرض می‌کنیم همه اعداد اول هستند. در طول اجرای الگوریتم، این آرایه به تدریج پر می‌شود.

حالا اعداد را از ۲ تا $n$ پیمایش می‌کنیم. برای عدد فعلی $i$ دو حالت داریم:

  • $lp[i] = 0$ - این یعنی $i$ یک عدد اول است، یعنی هیچ عامل کوچکتری برای آن پیدا نکرده‌ایم. بنابراین، $lp [i] = i$ را قرار می‌دهیم و $i$ را به انتهای لیست $pr[]$ اضافه می‌کنیم.

  • $lp[i] \neq 0$ - این یعنی $i$ عددی مرکب است و کوچکترین عامل اول آن $lp [i]$ است.

در هر دو حالت، مقادیر $lp []$ را برای اعدادی که بر $i$ بخش‌پذیر هستند به‌روزرسانی می‌کنیم. با این حال، هدف ما این است که یاد بگیریم این کار را طوری انجام دهیم که مقدار $lp []$ برای هر عدد حداکثر یک بار تنظیم شود. می‌توانیم این کار را به صورت زیر انجام دهیم:

اعداد $x_j = i \cdot p_j$ را در نظر بگیرید، که در آن $p_j$ تمام اعداد اول کوچکتر یا مساوی $lp [i]$ هستند (به همین دلیل است که باید لیست تمام اعداد اول را ذخیره کنیم).

برای تمام اعداد به این شکل، مقدار جدید $lp [x_j] = p_j$ را تنظیم می‌کنیم.

اثبات درستی این الگوریتم و زمان اجرای آن را می‌توان پس از پیاده‌سازی یافت.

پیاده‌سازی

const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;

for (int i=2; i <= N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back(i);
    }
    for (int j = 0; i * pr[j] <= N; ++j) {
        lp[i * pr[j]] = pr[j];
        if (pr[j] == lp[i]) {
            break;
        }
    }
}

اثبات درستی

باید ثابت کنیم که الگوریتم تمام مقادیر $lp []$ را به درستی تنظیم می‌کند و هر مقدار دقیقاً یک بار تنظیم خواهد شد. از این رو، الگوریتم زمان اجرای خطی خواهد داشت، زیرا تمام اقدامات باقیمانده الگوریتم، به وضوح در زمان $O(n)$ کار می‌کنند.

توجه داشته باشید که هر عدد $i$ دقیقاً یک نمایش به شکل زیر دارد:

$$i = lp [i] \cdot x$$

که در آن $lp [i]$ کوچکترین عامل اول $i$ است، و عدد $x$ هیچ عامل اولی کوچکتر از $lp [i]$ ندارد، یعنی:

$$lp [i] \le lp [x]$$

حال، بیایید این را با اقدامات الگوریتم خود مقایسه کنیم: در واقع، برای هر $x$، الگوریتم تمام اعداد اولی را که می‌توان در آن ضرب کرد (یعنی تمام اعداد اول تا $lp [x]$ به طور فراگیر) پیمایش می‌کند تا اعدادی به شکل بالا به دست آورد.

بنابراین، الگوریتم هر عدد مرکب را دقیقاً یک بار پیمایش کرده و مقادیر صحیح $lp []$ را در آنجا تنظیم می‌کند. اثبات کامل شد.

زمان اجرا و حافظه

اگرچه زمان اجرای $O(n)$ بهتر از $O(n \log \log n)$ غربال کلاسیک اراتستن است، تفاوت بین آنها چندان زیاد نیست. در عمل، غربال خطی تقریباً با همان سرعت یک پیاده‌سازی معمولی از غربال اراتستن اجرا می‌شود.

در مقایسه با نسخه‌های بهینه‌سازی‌شدهٔ غربال اراتستن، مانند غربال قطعه‌بندی‌شده (segmented sieve)، این الگوریتم بسیار کندتر است.

با توجه به نیازهای حافظه این الگوریتم - یک آرایه $lp []$ به طول $n$ و یک آرایه $pr []$ به طول $\frac n {\ln n}$ - به نظر می‌رسد این الگوریتم از هر نظر از غربال کلاسیک بدتر است.

با این حال، ویژگی برجسته آن این است که این الگوریتم آرایه $lp []$ را محاسبه می‌کند، که به ما امکان می‌دهد تجزیهٔ هر عدد در بازه $[2, n]$ را در زمانی از مرتبهٔ اندازهٔ تجزیهٔ آن پیدا کنیم. علاوه بر این، استفاده از تنها یک آرایهٔ اضافی به ما این امکان را می‌دهد که هنگام یافتن تجزیه، از عملیات تقسیم اجتناب کنیم.

دانستن تجزیهٔ تمام اعداد برای برخی مسائل بسیار مفید است و این الگوریتم یکی از معدود الگوریتم‌هایی است که امکان یافتن آن‌ها را در زمان خطی فراهم می‌کند.

مراجع

  • Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.