الگوریتم غربال
یکی از روش های تعیین اعداد اول در یک بازۀ عددی که در سال هشتم یاد میگیریم، استفاده از روش الگوریتم غربال میباشد. برای اینکه این روش را به خوبی یاد بگیریم در ادامه مراحل بدست آوردن اعداد اول 1 تا 40 توضیح داده شده است:
باید مضرب های اعداد اول را به ترتیب خط بزنیم:
ابتدا عدد 1 را که نه اول است و نه مرکب خط میزنیم. سپس مضرب های عدد 2 (به غیر از خودش) را که همگی مرکب هستند، خط میزنیم. توجه داشته باشید که اولین مضرب 2 که خط میخورد 2 به توان 2 یا 4 میباشد.
همه مضرب های 3 (به غیر از خودش) را خط میزنیم. توجه کنید که مضرب های 6، 12، 18 و … به خاطر اینکه مضرب 2 نیز هستند، در مرحله قبل خط خورده اند. اولین عددی که در این مرحله خط میخورد، عدد 3 به توان 2 یا 9 است.
مضرب های 5 (به غیر از خودش) را خط میزنیم. بعضی از مضرب های 5 مانند 10، 15، 20 و … قبلا خط خورده اند. اولین مضرب 5 که خط میخورد، عدد 5 به توان 2 یا 25 است.
حال اگر بخواهیم مضارب 7 را خط بزنیم، اولین عددی که باید خط بخورد 7 به توان 2 یا 49 است که در بین اعداد نیست. پس الگوریتم کامل است و دیگر خط زدن را ادامه نمیدهیم.
اکنون دور اعداد باقی مانده را خط میکشیم. این اعداد، اعداد اول بین 1 تا 40 میباشند.
حال برای اینکه با سوالات تعیین اعداد اول بیشتر آشنا شویم، در ادامه به حل چند مثال مهم میپردازیم:
سوال 1:
اعداد اول 51 تا 70 را به کمک غربال مشخص کنید و به سوالات زیر پاسخ دهید:
الف) عدد 63 به کمک مضارب کدام عدد خط میخورد؟
ب) کدام عدد به عنوان آخرین عدد خط میخورد؟
پ) اولین عددی که به کمک مضارب 3 خط میخورد کدام است؟
ابتدا اعداد 51 تا 70 را مینویسیم. سپس مضارب اعداد اول (2، 3، 5 و 7) را به ترتیب خط میزنیم.
دقت کنید که چون 11 به توان 2 یا 121 از 70 بزرگ تر است، لازم نیست مضارب 11 بررسی شوند!
در مرحله اول مضرب های عدد 2 (به غیر از خودش) را خط میزنیم:
در مرحله دوم مضرب های عدد 3 (به غیر از خودش) را خط میزنیم:
در مرحله سوم مضرب های عدد 5 (به غیر از خودش) را خط میزنیم:
و در مرحله آخر باید مضرب های عدد 7 (به غیر از خودش) را خط بزنیم که همانطور که میبینیم قبلا همگی خط خورده اند. اعدادی که باقی مانده اند، اعداد اول 51 تا 70 هستن و فقط کافی است دور آنها را خط بکشیم:
حالا میتوانیم با توجه به مراحلی که انجام دادیم به پرسش های الف تا پ پاسخ دهیم:
الف) عدد 63 به کمک مضارب کدام عدد خط میخورد؟ 3
ب) کدام عدد به عنوان آخرین عدد خط میخورد؟ 65
پ) اولین عددی که به کمک مضارب 3 خط میخورد کدام است؟ 51
سوال 2:
اول یا مرکب بودن هر کدام را مشخص کنید. (به همراه راه حل) 129 113
با توجه به توضیحاتی که در کادر بالا میبینیم، ابتدا جذر حدودی عدد 113 را بدست میآوریم:
به این ترتیب مشخص میشود که باید بخش پذیری عدد 113 را بر اعداد اول کوچک تر یا مساوی 10 یعنی (2، 3، 5 و 7) بررسی کنیم:
و به این ترتیب چون عدد 113 بر هیچ یک از اعداد اول کوچکتر از 10 بخش پذیر نیست، پس عدد اول است.
حال به بررسی عدد 129 میپردازیم. مطابق بالا، ابتدا جذر حدودی عدد 129 را بدست میآوریم:
بخش پذیری عدد 129 را بر اعداد اول کوچک تر یا مساوی 11 یعنی (2، 3، 5، 7 و 11) بررسی میکنیم:
129 بر 3 بخش پذیر است پس یک عددمرکب میباشد و نیازی به بررسی سایر اعداد اول نوشته شده نیست.
1 دیدگاه
به گفتگوی ما بپیوندید و دیدگاه خود را با ما در میان بگذارید.
بسیار عالی