پیش از آن که در مورد شیوه نوشتن الگوریتم شمارش اعداد اول در جاوا اسکریپت صحبت کنیم، بهتر است توضیح کوتاهی در مورد خود اعداد اول بدهیم. اعداد اول اعدادی بزرگ‌تر از یک هستند که تنها بر خودشان و عدد یک بخش‌پذیر هستند. شما احتمالاً در طول دوران تحصیل با مفهوم اعداد اول آشنا شده‌اید، اما شاید ندانید کاربرد این اعداد چیست. یکی از کاربردهای اعداد اول به خصوص اعداد اول بسیار بزرگ، در رمزنگاری است. در این مقاله قصد داریم به بررسی یک مسئله در مورد اعداد اول بپردازیم.

الگوریتم شمارش اعداد اول در جاوا اسکریپت

در مسئله فوق خواسته شده است که تعداد اعداد اول کمتر از عدد غیر منفی n محاسبه شود. چندین روش برای حل مسئله فوق وجود دارد. ما در این نوشته تلاش می‌کنیم از غربال «اراتوستن» (Eratosthenes) برای حل آن کمک بگیریم.

الگوریتم شمارش اعداد اول در جاوا اسکریپت

اراتوستن (Eratosthenes) یک ریاضیدان، فیلسوف، تاریخدان، ورزشکار، شاعر و مخترع یونانی است که در سال 276 پیش از میلاد به دنیا آمده است. بخش عمده شهرت اراتوستن به خاطر محاسبه محیط کره زمین بر مبنای مشاهده سایه اجسام در شهرهای مختلف در روز یکسانی از سال بوده است. گفته می‌شود که واژه جغرافیا را وی ابداع کرده است. شاگردان وی در اسکندریه مصر او را Pentathlos به نام پهلوانی که پنج رویداد مختلف را به پایان برده است نامیده‌اند.

غربال اراتوستن

وی یک الگوریتم عالی برای یافتن همه اعداد اول بین 1 و هر عدد مفروض ابداع کرده است. برای مثال عدد 120 را در نظر بگیرید.

  1. ابتدا همه اعداد بین 1 و 120 را بنویسید.
  2. از عدد 2 شروع می‌کنیم و همه اعداد بزرگ‌تر را که مضربی از 2 باشد، حذف می‌کنیم.
  3. عدد بعدی که حذف نشده را پیدا می‌کنیم، آن را به لیست اعداد اول اضافه می‌کنیم و گام 1 را تکرار می‌کنیم.

در تصویر زیر طرز کار این غربال را می‌بینید.

الگوریتم شمارش اعداد اول در جاوا اسکریپت

نکته: هر بار که عدد n را پیدا می‌کنیم که حذف نشده است، نخستین مضرب آن عدد که حذف نشده باشد عدد n*n خواهد بود.

زمانی که عدد n را پیدا کنیم که n*n بزرگ‌تر از عدد مورد نظر ما در لیست باشد، به پایان کار خود رسیده‌ایم.

کدنویسی غربال اراتوستن

در این بخش مراحل مختلف برای کدنویسی غربال اراتوستن در جاوا اسکریپت را بررسی می‌کنیم.

گام 1: نوشتن همه اعداد تا n

فرض کنید n=10 است. به یاد داشته باشید که ما به دنبال تعداد اعداد اول کمتر از 10 هستیم و از این رو در 9 متوقف می‌شویم.

این کار با استفاده از متد ()key جاوا اسکریپت امکان‌پذیر است. بر مبنای مستندات جاوا اسکریپت می‌دانیم که متد ()key یک شیء جدید Array Iterator بازگشت می‌دهد که شامل کلیدهایی برای هر اندیس در آرایه است.

شاید کنجکاو باشید که چرا کار خود را از صفر آغاز کردیم، در حالی که باید از 2 آغاز می‌کردیم. چون در گام بعدی می‌خواهیم روی این اعداد حلقه تکرار تعریف کنیم و می‌خواهیم اندیسی که برای حلقه تکرار استفاده می‌کنیم با مقدار آن اندیس برابر باشد.

گام 2: آغاز از عدد 2 و حذف همه مضارب بعدی 2

در کد به جای حذف اعداد، می‌توانیم مقادیرشان را تغییر دهیم تا بهتر ببینیم چه اتفاقاتی رخ می‌دهد. زمانی که عددی حذف می‌شود، می‌توانیم مقدار رشته‌ای آن را به nope تغییر دهیم و بدین ترتیب معنی nope این است که عدد غیر اول است.

در این بخش کد فوق را خط به خط توضیح می‌دهیم.

در حلقه for کد زیر را داریم:

به طور معمول هنگامی که روی یک آرایه می‌چرخیم، می‌خواهیم کل آرایه را بررسی کنیم و از اندیس 0 آغاز می‌کنیم. در این مورد می‌خواهیم از عدد 2 آغاز کنیم و لذا از اندیس 2 شروع کرده‌ایم:

هنگامی که عدد n را پیدا کنیم که n*n بزرگ‌تر از آخرین عدد در آرایه باشد، دیگر عددی برای حذف کردن نخواهیم داشت. بنابراین می‌توانیم حلقه را متوقف کنیم.

حذف اعداد

کد حذف اعداد به صورت زیر است:

به خاطر داشته باشید که ما تصمیم گرفتیم اعداد را به صوت تغییر مقدارشان به nope حذف کنیم. در خط فوق به عدد nums[i] نگاه می‌کنیم تا ببینیم آیا حذف شده یا نه. اگر حذف نشده باشد، ادامه می‌دهیم.

در کد فوق فرض کنید i = 2 باشد. یک تکرارکننده جدید به نام j با مقدر اولیه i*i تعیین می‌کنیم. در نخستین تکرار حلقه عنصر موجود در num[j] را حذف می‌کنیم، یعنی مقدار آن را nope تنظیم می‌کنیم. سپس j را دو واحد افزایش می‌دهیم و با تعیین آن عدد به صورت nope آن را نیز حذف می‌کنیم. این کار را تا زمانی که به انتهای آرایه برسیم تکرار می‌کنیم.

بنابراین زمانی که i=2 باشد، نخستین بار که در حلقه وارد می‌شویم، آرایه مانند زیر خواهد بود:

الگوریتم شمارش اعداد اول

بار دوم به شکل زیر درمی‌آید:

الگوریتم شمارش اعداد اول

و بار سوم به صورت زیر خواهد بود:

الگوریتم شمارش اعداد اول

دفعه بعد که افزایش یابد، برابر با 10 خواهد بود که خارج از دامنه حلقه است. بنابراین به حلقه i بعدی می‌رویم که این بار i=3 است. مقدار j را روی مقدار اولیه i^2 یعنی 9 تعیین می‌کنیم و آن عدد را حذف می‌کنیم.

الگوریتم شمارش اعداد اول

سپس حلقه j همه مضارب بعدی را حذف می‌کند، اما مضرب بعدی 12 است که خارج از آرایه است و از این رو به حلقه i بعدی می‌رویم. عدد بعدی 5 است. دوباره به حلقه j می‌رسیم و تلاش می‌کنیم تا i*i یعنی 25 را حذف کنیم که چنان که می‌بینید، خارج از دامنه آرایه است.

اگر به حلقه i بازگردیم به عدد i=7 رسیده‌ایم و با بررسی i*i می‌بینیم که عدد 49 خارج از حلقه قرار دارد. بنابراین به انتهای آرایه رسیده‌ایم.

گام 3: تبدیل آرایه اعداد به لیستی از اعداد اول

اینک باید آرایه ما به صورت زیر در آمده باشد:

الگوریتم شمارش اعداد اول

آن را به صورت زیر درمی‌آوریم:

[2,3,5,7]

به این منظور می‌توانیم روی آرایه حلقه‌ای تعریف کنیم و هر عنصری که بزرگ‌تر از 1 است را برداریم:

گام 4: بازگشت طول آرایه

در صورت مسئله آمده بود که باید تعداد اعداد اول بین 1 و n را بازگشت دهیم و نه خود اعداد را. بنابراین از متد ()length. در جاوا اسکریپت استفاده می‌کنیم:

اینک در مجموع کدهای زیر را داریم:

افزایش سرعت الگوریتم

بر اساس گزارش LeetCode، کد فوق برای اجرا به 200 میلی‌ثانیه زمان نیاز دارید که کاملاً کند است. با تغییر دادن روش حذف اعداد می‌توانیم سرعت اجرای الگوریتم را افزایش دهیم. بدین ترتیب اعداد حذف شده را به عدد 1 تغییر می‌دهیم.

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

الگوریتم شمارش اعداد اول

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

telegram
twitter

میثم لطفی

«میثم لطفی» دانش‌آموخته ریاضیات و شیفته فناوری به خصوص در حوزه رایانه است. وی در حال حاضر علاوه بر پیگیری همه علاقه‌مندی‌های خود در رشته‌های برنامه‌نویسی، کپی‌رایتینگ و تولید محتوای چندرسانه‌ای، در زمینه نگارش مقالاتی با محوریت نرم‌افزار نیز با مجله فرادرس همکاری دارد.

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *