پیدا کردن $n$اُمین عدد خط خورده در روش غربال اِراتُستِن

Question

چگونه باید $n$اُمین عدد خط‌خورده بوسیلهٔ اَلَک (غربال) اراتستن را پیدا کنیم؟ برای نمونه پرسش زیر را در نظر بگیرید.

اعداد ۱ تا ۴۰ را نوشته سپس با استفاده از روش غربال اراتسن، اعداد اول را مشخص می‌کنیم. بیست و هفتمین عددی که در جریان استفاده از این غربال خط می‌خورد کدام عدد است؟

Answer 1

فرض کنید اعداد یک تا چهل را نوشته ایم. بیایید باهم بررسی کنیم که چگونه اعداد خط میخورند.

ابتدا از دو شروع میکنیم. خودش اول است ما باید هر عدد به صورت 2k را خط بزنیم پس: $2k \leq 400 \Longrightarrow k \leq 20$

که عدد یک حساب نمیشود پس ۱۹ تا خط خورده اند. حال می رویم سراغ 3 تمامی مضارب 3 خط میخورند پس: $3k \leq 40 \Longrightarrow k \leq 13$

که تعدادش12 تا است اما نکته مهم این است که عددی وجود دارد که بر 3 و 2 بخش پذیر است $6k \leq 40 \Longrightarrow k \leq 6$

پس باید نوشت: $31-6=25$

یعنی زمانی که آخرین مضرب سه خط می خورد 25 تا عدد خورده اند.پس 27 امین عدد 35 است.