الگوریتم غربال

Question

اگه بخواهیم اعداد بین aوb رو درنظر بگیریم که a و b هردو از یک بزرگترند، و به روش غربال ، آخرین عددی که خط میخوره و همینطور nامین عددی که خط میخوره رو پیدا کنیم ،چطوری انجام بدیم.

Answer 1

برای بدست آوردن آخرین عددی که خط میخورد باید بزرگترین عدد اولی را پیدا کنیم که از $\sqrt{b}$ کمتر باشد. فرض کنید این عدد اول برابر $p$ باشد حال بزرگترین عدد اول کمتر یا مساوی $\frac{b}{p}$ را می یابیم. اگر این عدد برابر $q$ باشد آنگاه $pq$ آخرین عدد حذف شده در غربال خواهد بود.

به طور مثال برای اعداد بین 40 تا 240 ابتدا داریم $\sqrt{240} \simeq 15.49$پ س در اینجا $p=13$ و همچنین $\frac{240}{13} \simeq 18.46$ پس نزدیک ترین عدد اول برابر 17 است پس $q=17$

آخرین عددی که خط می خورد برابر است با $13 \times 17=221$

فرمول کلی برای غربال رو بلد نیستم اما برای حالت های خاص میتوانید سوال چگونه سوالات مربوط به غربال را حل کنیم؟ را نگاه نمایید.