درس نهم: روش حل مسأله قسمت دوم

در این قسمت مساله پیدا کردن اعداد اول رو ادامه میدیم و الگوریتم آن را بهینه میکنیم.

ابتدا با یک الگوریتم ساده برای پیدا کردن اعداد اول شروع می‌کنیم و سپس به تدریج آن را بهینه می‌کنیم.

الگوریتم اولیه (روش بررسی ساده)

این الگوریتم به سادگی برای هر عدد بررسی می‌کند که آیا مقسومی جز ۱ و خودش دارد یا خیر.

function findPrimesSimple(limit) {
  let primes = [];
  for (let i = 2; i <= limit; i++) {
    let isPrime = true;
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(i);
    }
  }
  return primes;
}

console.log(findPrimesSimple(50)); // نتیجه: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

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

بهینه‌سازی ۱: کاهش تعداد مقسوم‌ها تا جذر عدد

برای اعداد بزرگتر از ۱، کافیست مقسوم‌ها را تا جذر عدد بررسی کنیم، زیرا اگر عددی به مقسومی بزرگتر از جذر خود تقسیم شود، مقسوم دیگری در بازه کوچک‌تر هم دارد.

function findPrimesOptimized(limit) {
  let primes = [];
  for (let i = 2; i <= limit; i++) {
    let isPrime = true;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(i);
    }
  }
  return primes;
}

console.log(findPrimesOptimized(50)); // نتیجه: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

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

بهینه‌سازی ۳: استفاده از اعداد فرد به جای همه اعداد

می‌توانیم برای بهینه‌سازی بیشتر، تنها اعداد فرد را بررسی کنیم. زیرا همه اعداد زوج (به جز ۲) نمی‌توانند اول باشند.

function findPrimesEfficient(limit) {
  if (limit < 2) return [];
  let primes = [2];
  for (let i = 3; i <= limit; i += 2) {
    let isPrime = true;
    for (let j = 3; j <= Math.sqrt(i); j += 2) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(i);
    }
  }
  return primes;
}

console.log(findPrimesEfficient(50)); // نتیجه: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

در این نسخه، با افزایش گام به جای بررسی همه اعداد، تنها اعداد فرد بررسی می‌شوند که باعث می‌شود الگوریتم بهینه‌تر و سریع‌تر باشد.

جمع‌بندی

الگوریتم «غربال اراتوستن» بهینه‌ترین و سریع‌ترین راه برای پیدا کردن اعداد اول تا حد مشخصی است و در پروژه‌های بزرگ‌تر، برای پیدا کردن اعداد اول پیشنهاد می‌شود.