فرض کنیم یه عدد به ما دادن ، مثلا عدد 50، و از ما میخوان همه اعداد اول کمتر از 50 رو محاسبه کنیم. چکار کنیم؟
ما که نمیتونیم دونه دونه عددا رو تجزیه کنیم و ببینیم چه شمارنده هایی دارن . البته میشه این کار رو انجام داد ولی خیلی طول میکشه
یه روش داریم به اسم روش غربال، که برای به دست آوردن اعداد اول ازش استفاده میشه.
برای استفاده از روش غربال، اعداد رو تا جایی که خواسته شده مینویسیم.
مثلا اینجا اعداد رو از 1 تا 50 مینویسیم و بعد به صورت زیر عمل میکنیم:
گام اول :
میدونیم عدد 1 اول نیست، پس خطش میزنیم.
گام دوم :
میدونیم عدد 2 اوله. از طرفی میدونیم که غیر از 2 هیچ عدد زوج دیگه ای اول نیست ( چون غیر از خودش و 1 ، بر 2 هم بخشپذیره)
پس در گام دوم میایم همه اعداد زوج غیر از 2 رو خط میزنیم.
گام سوم :
میدونیم عدد 3 اوله، اما بقیه مضربهای عدد 3 ، هیچکدوم اول نیستن. چرا؟
چون غیر از خودشون و 1 ، بر 3 هم بخشپذیرن.
پس در گام سوم، همه مضربهای 3، غیر از خود 3 رو حذف میکنیم
تا اینجا مضربهای 2 و 3 رو حذف کردیم. به نظرتون الان باید مضربهای 4 رو حذف کنیم؟
مضربهای عدد 4 همشون زوجن و م
