اعداد اول به روش غربال

تعیین اعداد اول به روش غربال چگونه است؟
مثال: اعداد اول بین 1 تا 60 را به روش غربال پیدا کنید.
پاسخ: ابتدا اعداد رو از 1 تا 60 به صورت مرتب مینویسیم. برای تعیین اعداد اول به روش غربال، طی چند مرحله که الان کامل براتون توضیح میدم شروع می کنیم به خط زدن مضرب های عددهای اول معروف یعنی همون 2، 3، 5، 7، 11، 13، 17، 19 ‌و … که در واقع عددهایی که خط میزنیم اول نیستن و آخر کار هرچی که خط نخورده باقی میمونه عدد اول هست. مراحل کار رو به ترتیب باهم دنبال می کنیم:
1) اول از همه عدد 1 رو خط میزنیم چون این عدد نه اول هست و نه مرکب. پس همیشه خطش میزنیم.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
2) بعد میریم به سراغ خط زدن مضرب های عدد 2 که در واقع همون اعداد زوج هستن. هرچی عدد زوج داریم خط میزنیم. یادتون باشه که خود عدد 2 رو خط نزنید ها! اون یه عدد اول خودش.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
3) بریم سراغ مضرب های عدد 3 که الان باید خط بخورند، البته همه بجز خود عدد 3، چون 3 یک عدد اول هست. همه اعدادی که مجموع رقم ها بر 3 بخش پذیر هست رو خط میزنم. چون شرط بخش پذیری بر 3،که مجموع رقم های عدد بر 3 بخش پذیر باشد. هر عددی که بر 3 بخش پذیر باشدیعنی اینکه مضرب 3 هستد.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
4) برویم سراغ مضرب های عدد 5 که الان باید خط بخورند بجز خود عدد 5، چون 5 یک عدد اول هست. همه اعدادی که رقم یکان آنها صفر یا 5 باشه خط میزنم. چون شرط بخش پذیری بر 5. هر عددی که بر 5 بخش پذیر باشد یعنی اینکه مضرب 5 هست. مضرب های 5، پنج تا پنج تا جلو برو. پس ما برای خط زدن از عدد 5 شروع می کنیم پنج تا پنج تا میشماریم و عددها رو خط میزنیم. اگر به عددی رسیدیم که قبلا خط خورده مشکلی پیش نمیاید ما به شمردن خود ادامه میدهیم.
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
5) موضوعی هست که ما تا کی باید این خط زدن ها رو ادامه بدیم؟ قطعا اینطوری نیست که تا هرجا دلمان خواست خط بزنیم، هر وقت خسته شدیم دیگه خط نزنیم. یه راهکاری دارد. اگریه عدد اول رو در خودش ضرب کردیم و دیدیم که جواب از آخرین عدد کوچکتر است، یعنی مضرب های ان عدد اول راباید خط بزنیم. اگر هم که حاصلضرب عدد اول در خودش بیشتر از عدد آخری شد یعنی کار غربال کردن تمام شده و هرچه عدد خط نخورده داریم عدد اول هستش.
واسه این مثال که داشتیم حل می کردیم:
2 × 2 = 4 < 60 ⇒ مضرب های 2 باید خط بخورند.
3 × 3 = 9 < 60 ⇒ مضرب های 3 باید خط بخورند.
5 × 5 = 25 < 60 ⇒ مضرب های 5 باید خط بخورند.
7 × 7 = 49 < 60 ⇒ مضرب های 7 باید خط بخورند.
11 × 11 = 121 > 60 ⇒ نیاز به خط زدن مضرب های 11 نیست و کار غربال تمام است.
پس لازمه که مضرب های 7 راهم خط برنیم. از 7 شروع به شمردن می کنیم، هفت تا هفت تا جلو میریوم و خط میزنیم. اگه قبلا خط خورده بود اشکالی پیش نمیاید.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
اعدادی که خط نخورده باقی مونده رو به رنگ آبی نشان دادیم. 2، 3، 5، 7، 11، 13، 17، 19، 23، 29، 31، 37، 41، 43، 47، 53، 59 اعداد اول هستند.