تبلیغات
ریاضی سوم راهنمایی - الگوریتم غربال
« : d F Y »

اعداد اول یکی از شگرفترین مفاهیم ریاضی هستند که همواره قدرت ریاضیدانان و برنامه نویسان را به چالش کشیده است. سختی تولید این اعداد باعث شده است همواره افراد سعی در فرموله کردن آن ها داشته به دنبال الگوریتم های قدرمندتری برای تولید آن ها باشند. یکی از قدیمیترین و کاراترین الگوریتم تولید اعداد اول، الگوریتم غربال است که هم اکنون انواع بهبود یافته آن به عنوان سریعترین روش تولید اعداد اول استفاده می شوند. ما برای درک بهتر  این الگوریتم از ساده ترین آن شروع می کنیم و به مرور زمان ضمن تلاش خودمان برای بهبود آن، از انواع بهبود یافته که در برنامه های مختلف کابرد دارند استفاده خواهیم کرد.

-- الگوریتم --

روش غربال همانطور که از نام آن بر می آید با حذف اعداد مرکب ، اعداد باقی مانده را به عنوان اعداد اول معرفی می کند. با عدد 2 شروع می کنیم و تمام مضارب آن را علامت می زنیم، سپس با عدد 3 همین کار را انجام می دهیم و تا جذر عدد N ) N همان عددیست که می خواهیم اعداد اول تا آن را پیدا کنیم ) پیش می رویم ( چرا تا جذر N ؟ ) . و این نکته را ( به عنوان یک بهبود زمان از نوع حذف عملیات ) مد نظر داریم که تنها مضارب اعدادی را حذف می کنیم که خود عدد، عدد اول باشد. چرا که اگر عدد اول نباشد ما عملیات بیهوده ای انجام داده ایم و مضارب یک عدد مرکب توسط عامل های آول آن عدد علامت زده می شوند. در این روش چون فقط به یک علامت نیاز داریم پس کمترین حجم ممکن را برای این Flag در نظر می گیریم ، در این جا 1 بایت ( 1 بایت خود شامل 8 بیت است که می توانیم با تعدادی عمل اضافی به جای 1 بایت از یک هشتم آن یعنی یک بیت استفاده کنیم. این مورد را در ارسال های بعدی بررسی می کنیم.) فضا از نوع Char را لحاظ می کنیم. پس تا اینجا به ازای عدد N، نیاز به N بایت فضا داریم. ( اعداد زوج به سادگی قابل حذف هستند که باعث نصف شدن فضای مورد نیاز می شوند. این مورد هم در ارسال ها بعدی بررسی می شود.). چون Flag ما در اینجا عدد 1 است پس هر خانه ای از آرایه که مقدار اولیه خود ( در این جا 0 ) را داشته باشد، یعنی علامت نخورده است پس عدد اول است. متغیر div هم تعیین می کند عملیات حذف مضارب یک عدد اول تا کجا پیش رود. اگر به داخلی ترین دستور درون if داخلی نگاه کنید، میبینید که عملیات مورد استفاه جمع است. چرا جمع؟ مگر قرار نبود مضارب حذف شوند؟ مگر مضارب با ضرب تولید نمی شوند؟ بله درست است. مضارب با ضرب تولید می شوند ولی زمانی که یک عدد ثابت ( در این جا i ) قرار است در اعداد 2 ، 3 ، 4 ، 5، و .. ضرب شود ( اختلاف اعداد یک واحد است ) پس در هر مرحله مقداری معادل عدد ثابت باید افزوده شود ( s+=i ) که اینکار با جمع هم قابل اجراست. وقتی می توانیم یک عملیات را با جمع انجام دهیم ، چرا به سراغ ضرب برویم. تصور کنید می خواهید i را در 1569 ضرب کنید. در این برنامه ما در مرحله قبلی حاصل ضرب i در 1568 را بدست آورده ایم. خوب وقتی می توانیم با یک بار افزودن i به جواب قبلی، جواب این مرحله را داشته باشیم، چه لزومی دارد i را 1569 ضرب کنیم. حالا این کاهش عملیات را برای تمام اعداد اول تا N محاسبه کنید که خواهید دید چقدر این حقه ساده در کاهش زمان برنامه موثر است. به همین سادگی. حلقه اصلی دوم هم تعداد اعداد اول تا N را می شمارد و در صورتی که دستور printf موجود در آن را از حالت comment خارج کنید، تمام اعداد اول تا N را نیز چاپ می کند ( البته به غیر از اولین عدد اول یعنی 2