الگوریتم غربالگری اعداد اول
در روش غربالگری اعداد اول، ابتدا لیستی از اعداد طبیعی از 2 تا عدد مورد نظر (در اینجا 70) تهیه می‌کنیم. سپس:
- عدد 2 را به عنوان اولین عدد اول انتخاب می‌کنیم و تمام مضرب‌های آن را خط می‌زنیم.
- به عدد بعدی که خط نخورده است می‌رویم (عدد 3) و تمام مضرب‌های آن را خط می‌زنیم.
- این روند را تا رسیدن به عددی که مربع آن از 70 بزرگتر باشد (یعنی 8.37، پس عدد 9) ادامه می‌دهیم.
برای یافتن رتبه عدد 39 در این الگوریتم، باید ببینیم چند عدد اول قبل از آن وجود دارد و چند عدد غیر اول قبل از آن خط خورده‌اند.
اعداد اول کمتر از 70: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67
عدد 39 مضرب 3 و 13 است. پس به عنوان یک عدد غیر اول خط خواهد خورد.
قبل از عدد 39، اعداد اول و غیر اول زیادی خط خورده‌اند. برای شمارش دقیق باید اعداد را بررسی کنیم.
با شمارش اعداد اول و غیر اول تا 39، می‌توان فهمید که 39 چندمین عددی است که خط می‌خورد.
با شمارش، مشخص می‌شود که عدد 39، 33مین عددی است که خط می‌خورد.
یادآوری ایمنی: در انجام محاسبات ریاضی دقت کافی داشته باشید.
