فرض کنیم یه عدد به ما دادن ، مثلا عدد 50، و از ما میخوان همه اعداد اول کمتر از 50 رو محاسبه کنیم. چکار کنیم؟
ما که نمیتونیم دونه دونه عددا رو تجزیه کنیم و ببینیم چه شمارنده هایی دارن . البته میشه این کار رو انجام داد ولی خیلی طول میکشه
یه روش داریم به اسم روش غربال، که برای به دست آوردن اعداد اول ازش استفاده میشه.
برای استفاده از روش غربال، اعداد رو تا جایی که خواسته شده مینویسیم.
مثلا اینجا اعداد رو از 1 تا 50 مینویسیم و بعد به صورت زیر عمل میکنیم:
گام اول :
میدونیم عدد 1 اول نیست، پس خطش میزنیم.
گام دوم :
میدونیم عدد 2 اوله. از طرفی میدونیم که غیر از 2 هیچ عدد زوج دیگه ای اول نیست ( چون غیر از خودش و 1 ، بر 2 هم بخشپذیره)
پس در گام دوم میایم همه اعداد زوج غیر از 2 رو خط میزنیم.
گام سوم :
میدونیم عدد 3 اوله، اما بقیه مضربهای عدد 3 ، هیچکدوم اول نیستن. چرا؟
چون غیر از خودشون و 1 ، بر 3 هم بخشپذیرن.
پس در گام سوم، همه مضربهای 3، غیر از خود 3 رو حذف میکنیم
تا اینجا مضربهای 2 و 3 رو حذف کردیم. به نظرتون الان باید مضربهای 4 رو حذف کنیم؟
مضربهای عدد 4 همشون زوجن و ما توی گام دوم همه اعداد زوج غیر از 2 رو خط زدیم. بنابراین همه مضربهای 4 در گام دوم خط خوردن.
گام چهارم:
عدد 5 اوله ولی بقیه مضربهای 5 هیچکدوم اول نیستن، چون غیر از خودشون و 1 به 5 هم بخشپذیرن. پس همه مضربهای 5 غیر از 5 رو حذف میکنیم
چون عدد 6 و مضربهاش همگی زوج هستند و در مرحله 2 حذف شدن، پس نیازی نیست که دنبالشون بگردیم
گام پنجم:
عدد 7 اوله ولی بقیه مضربهای 7 اول نیستن و باید خط بخورن و البته خیلیاشون در مراحل قبل خط خوردن
پس داریم:
اعدادی که باقی موندن همگی اول هستن.
بنابراین اعداد اول کمتر از 50 عبارتند از :
47 ، 43 ، 41 ، 37 ، 31 ، 23،29 ، 19 ، 17 ، 13 ، 11 ، 7 ، 5 ، 3 ، 2
یه سوال مهم: ما مضربهای 2 و 3 و 5 و 7 رو خط زدیم. آیا باز هم باید مضربهای بقیه اعداد اول رو خط بزنیم؟ مثلا در مثال قبل باید مضربهای 11 و 13 و … رو پیدا کنیم و حذف کنیم؟
برای اینکه بفهمیم مضربهای بقیه اعداد اول رو باید خط بزنیم یا نه، به صورت زیر عمل کنیم:
اولین عدد اولی که برامون مونده و خط نخورده رو پیدا میکنیم، این عدد چیه؟ 11
مربع این عدد رو به دست میاریم ، برابر میشه با 121
نگاه میکنیم ببینیم مربع 11 بین اعدادمون هست یا نه؟ آیا 121 بین اعدامون هست؟ خیر ، چون اعدادی که داریم کمتر از 50 هستن، پس دیگه ادامه نمیدیم.
اگه 121 بین اعدادمون بود باید چکار میکردیم؟ باید مضربهای 11 رو حذف میکردیم و میرفتیم سراغ عدد اول بعدی.
