۱- از روش غربال برای عددهای ۱ تا ۶۰ استفاده و عددهای اول کمتر از ۶۰ را پیدا کنید.
روش غربال اراتستن (Sieve of Eratosthenes) روشی برای پیدا کردن اعداد اول است. برای اعداد ۱ تا ۶۰، مراحل زیر را انجام می‌دهیم:
۱. **تعیین محدوده:** ابتدا بزرگ‌ترین عدد اولی که باید مضرب‌هایش را خط بزنیم پیدا می‌کنیم. این عدد از $ \sqrt{۶۰} $ بزرگ‌تر نیست. چون $ \sqrt{۶۰} \approx ۷.۷ $، ما فقط مضرب‌های اعداد اول **۲، ۳، ۵ و ۷** را بررسی می‌کنیم.
۲. **مراحل غربال:**
- ابتدا عدد ۱ را خط می‌زنیم.
- مضرب‌های مرکب ۲ را خط می‌زنیم (تمام اعداد زوج به جز ۲).
- مضرب‌های مرکب ۳ را خط می‌زنیم (تمام مضرب‌های ۳ به جز خود ۳).
- مضرب‌های مرکب ۵ را خط می‌زنیم (تمام مضرب‌های ۵ به جز خود ۵).
- مضرب‌های مرکب ۷ را خط می‌زنیم (تمام مضرب‌های ۷ به جز خود ۷).
۳. **اعداد اول باقی‌مانده:**
اعدادی که پس از این مراحل خط نخورده باقی می‌مانند، اعداد اول کوچک‌تر از ۶۰ هستند. این اعداد عبارتند از:
**$ \{ ۲, ۳, ۵, ۷, ۱۱, ۱۳, ۱۷, ۱۹, ۲۳, ۲۹, ۳۱, ۳۷, ۴۱, ۴۳, ۴۷, ۵۳, ۵۹ \} $**
۲- مشخص کنید که عددهای ۱۰۷ و ۲۵۱ اول‌اند یا مرکب.
برای تشخیص اول یا مرکب بودن یک عدد، آن را بر اعداد اولی تقسیم می‌کنیم که مربعشان از آن عدد کوچک‌تر یا مساوی باشد.
- **بررسی عدد ۱۰۷:**
۱. $ \sqrt{۱۰۷} \approx ۱۰.۳ $. بنابراین باید بخش‌پذیری ۱۰۷ را بر اعداد اول کوچک‌تر از ۱۰.۳ یعنی **۲، ۳، ۵ و ۷** بررسی کنیم.
۲. ۱۰۷ بر هیچ‌یک از اعداد ۲ (چون فرد است)، ۳ (چون جمع ارقامش $۱+۰+۷=۸$ است)، ۵ (چون یکانش ۷ است) و ۷ بخش‌پذیر نیست.
۳. **نتیجه:** **۱۰۷ عددی اول است.**
- **بررسی عدد ۲۵۱:**
۱. $ \sqrt{۲۵۱} \approx ۱۵.۸ $. بنابراین باید بخش‌پذیری ۲۵۱ را بر اعداد اول کوچک‌تر از ۱۵.۸ یعنی **۲، ۳، ۵، ۷، ۱۱ و ۱۳** بررسی کنیم.
۲. ۲۵۱ بر هیچ‌یک از اعداد ۲، ۳، ۵، ۷، ۱۱ و ۱۳ بخش‌پذیر نیست.
۳. **نتیجه:** **۲۵۱ عددی اول است.**
۳- «برای اینکه بفهمیم عددهای کمتر از ۱۰۰ اول‌اند یا نه، کافی است آنها را به عددهای ۲، ۳، ۵ و ۷ تقسیم کنیم.»
آیا این جمله درست است؟ چرا؟
**بله، این جمله درست است.**
**چرا؟**
برای تشخیص اول بودن هر عدد $n$، کافی است بخش‌پذیری آن را بر اعداد اول کوچک‌تر یا مساوی $ \sqrt{n} $ بررسی کنیم.
در این سوال، ما اعداد کوچک‌تر از ۱۰۰ را بررسی می‌کنیم، پس بزرگ‌ترین عدد مورد بررسی ما ۹۹ است.
$ \sqrt{۹۹} \approx ۹.۹۵ $
اعداد اولی که کوچک‌تر یا مساوی ۹.۹۵ هستند، عبارتند از: **۲، ۳، ۵ و ۷**.
بنابراین، برای هر عددی که کوچک‌تر از ۱۰۰ باشد، اگر بر هیچ‌یک از اعداد ۲، ۳، ۵ و ۷ بخش‌پذیر نباشد، آن عدد اول است. در نتیجه، تقسیم بر این چهار عدد کافی است.
۴- عددی از ۱۲۰ کوچک‌تر و از ۱۰۰ بزرگ‌تر است. برای اینکه بفهمیم این عدد اول است یا نه، حداکثر چند تقسیم انجام می‌دهیم؟ چرا؟
حداکثر **۴ تقسیم** انجام می‌دهیم.
**چرا؟**
برای فهمیدن اینکه عددی اول است یا نه، باید آن را بر اعداد اول تا جذر خودش تقسیم کنیم. در این سوال، ما عددی بین ۱۰۰ و ۱۲۰ را بررسی می‌کنیم. برای اینکه حداکثر تعداد تقسیم‌ها را پیدا کنیم، باید بزرگ‌ترین عدد ممکن در این بازه یعنی **۱۱۹** را در نظر بگیریم.
$ \sqrt{۱۱۹} \approx ۱۰.۹ $
اعداد اولی که کوچک‌تر یا مساوی ۱۰.۹ هستند عبارتند از **۲، ۳، ۵ و ۷**. بنابراین، با بررسی بخش‌پذیری بر این **۴ عدد اول**، می‌توانیم اول بودن هر عددی در این بازه را مشخص کنیم.
۵- عددهای ۱ تا ۱۰۰ را بنویسید و غربال کنید؛ سپس به سؤال‌های زیر پاسخ دهید.
- اولین عددی که خط می‌خورد.
- در مرحلۀ حذف مضرب‌های ۷، اولین مضرب ۷ که به عنوان مضرب‌های سایر عددها خط نخورد.
- عددی که با مضرب‌های آن عدد ۲۴ خط خورد.
- تمام مضرب‌های ۵ که در مرحلۀ حذف مضرب‌های ۵ برای اولین بار خط خوردند.
پاسخ‌ها بر اساس اجرای روش غربال برای اعداد ۱ تا ۱۰۰ به دست می‌آید:
- **اولین عددی که خط می‌خورد:**
عدد **۱** است، زیرا طبق تعریف نه اول است و نه مرکب.
- **در مرحلۀ حذف مضرب‌های ۷، اولین مضرب ۷ که به عنوان مضرب‌های سایر عددها خط نخورد:**
عدد **۴۹** است ($۴۹ = ۷ \times ۷$). زیرا مضرب‌های کوچک‌تر ۷ (مانند ۱۴، ۲۱، ۲۸، ۳۵، ۴۲) قبلاً به عنوان مضرب اعداد اول کوچک‌تر (۲، ۳ و ۵) خط خورده‌اند.
- **عددی که با مضرب‌های آن عدد ۲۴ خط خورد:**
عدد **۲** است. در روش غربال، هر عدد مرکب با کوچک‌ترین شمارنده اول خود خط می‌خورد. کوچک‌ترین شمارنده اول ۲۴، عدد ۲ است.
- **تمام مضرب‌های ۵ که در مرحلۀ حذف مضرب‌های ۵ برای اولین بار خط خوردند:**
این‌ها مضرب‌هایی از ۵ هستند که شمارنده اولی کوچک‌تر از ۵ (یعنی ۲ یا ۳) ندارند. این اعداد عبارتند از:
**$ ۲۵, ۳۵, ۵۵, ۶۵, ۸۵, ۹۵ $**
امیررضا کاظمی
1403/08/18
عالی خیلی خوب