জাভাস্ক্রিপ্টে সিয়ভ অফ এরাটোস্থেনিস দিয়ে প্রাইম নম্বর বের করা

সমস্যা বিবরণ

একটি নম্বর n দেওয়া আছে। ১ থেকে n পর্যন্ত সব প্রাইম নম্বর বের করতে হবে। সিয়ভ অফ এরাটোস্থেনিস অ্যালগরিদম ব্যবহার করা হয়েছে।

সমাধান

const num = 100;

const findPrimes = (num = 10) => {
  const numArr = new Array(num + 1);
  numArr.fill(true);
  numArr[0] = numArr[1] = false;
  
  for (let i = 2; i <= Math.sqrt(num); i++) {
    for (let j = 2; i * j <= num; j++) {
      numArr[i * j] = false;
    }
  }
  
  return numArr.reduce((acc, val, ind) => {
    if (val) return acc.concat(ind);
    else return acc;
  }, []);
};

console.log(findPrimes(num));

আউটপুট

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]

অ্যালগরিদম ব্যাখ্যা

• বুলিয়ান অ্যারে তৈরি করে সবকে true দিয়ে শুরু।
• ২ থেকে sqrt(n) পর্যন্ত লুপ: প্রতিটি প্রাইমের মাল্টিপ্লাইগুলো false করে দাও।
• শেষে true ইনডেক্সগুলো প্রাইম নম্বর।
• টাইম কমপ্লেক্সিটি: O(n log log n) - খুব দক্ষ।