یافتن اعداد اول با استفاده از الگوریتم غربال اراتوستن

اعداد اول، اعداد طبیعی بزرگ‌تر از ۱ هستند که هیچ مقسوم‌علیه مثبتی جز ۱ و خودشان ندارند؛ مانند ۲، ۳، ۵ و ۷. این اعداد در حوزه‌های مختلفی کاربرد دارند، از جمله رمزنگاری برای ارتباطات امن، ریاضیات در نظریه اعداد، علوم کامپیوتر در توابع هش و الگوریتم‌ها، تشخیص خطا در انتقال داده، و پردازش سیگنال.

با این حال، محاسبه اعداد اول، به‌ویژه اعداد بزرگ، بسیار چالش‌برانگیز و از نظر محاسباتی سنگین است. امروز الگوریتم غربال اراتوستن را بررسی می‌کنیم؛ روشی کارآمد برای یافتن اعداد اول.

غربال اراتوستن چیست؟

غربال اراتوستن یک الگوریتم کارآمد برای یافتن تمام اعداد اول تا یک حد مشخص است. این الگوریتم با علامت‌گذاری تکراری مضرب‌های هر عدد اول به‌عنوان مرکب (غیر اول)، از عدد ۲ شروع می‌کند. این الگوریتم به افتخار اراتوستن کورنی، ریاضیدان یونانی قرن سوم قبل از میلاد، نام‌گذاری شده است.

پیاده‌سازی غربال در TypeScript

در اینجا پیاده‌سازی پایه این الگوریتم در TypeScript آورده شده است:

۱. یک آرایه بولی به نام table با limit + 1 عنصر می‌سازیم که ابتدا همه مقادیر آن true است. ۲. از آنجایی که ۰ و ۱ عدد اول نیستند، عناصر صفرم و اول آرایه را false می‌کنیم. ۳. از ۲ تا جذر حد تکرار می‌کنیم، زیرا هر عدد مرکب بزرگ‌تر از √limit باید یک عامل کوچک‌تر یا مساوی √limit داشته باشد. ۴. برای هر عدد اول یافت‌شده، تمام مضرب‌های آن را به‌عنوان مرکب علامت‌گذاری می‌کنیم. ۵. در نهایت، تمام اعدادی که هنوز به‌عنوان اول علامت‌گذاری شده‌اند را در یک آرایه جمع‌آوری کرده و برمی‌گردانیم.

function sieveOfEratosthenes(limit: number): number[] {
  const table: boolean[] = Array(limit + 1).fill(true);

  table[0] = table[1] = false;

  for (let n = 2; n ** 2 <= limit; n++) {
    for (let k = n ** 2; k <= limit; k += n) {
      table[k] = false;
    }
  }

  const primes: number[] = [];

  for (let n = 2; n <= limit; n++) {
    if (table[n]) {
      primes.push(n);
    }
  }

  return primes;
}

پیچیدگی زمانی و فضایی

پیچیدگی زمانی این پیاده‌سازی O(n log log n) است، که در آن n حد ورودی است. این الگوریتم را نسبت به رویکردهای ساده‌ای که هر عدد را جداگانه بررسی می‌کنند، کارآمدتر می‌کند.

پیچیدگی فضایی O(n) است، زیرا از یک آرایه به اندازه n+1 برای ذخیره مقادیر بولی استفاده می‌کنیم.

و همین! حالا می‌دانید چگونه با استفاده از این الگوریتم جالب، اعداد اول را به‌سرعت محاسبه کنید.