مقدمه
شما در یک حراجی خانگی، یک جعبهی بزرگ پر از قطعات کامپیوتری درهموبرهم خریدهاید. حالا شروع کردهاید این قطعات را سر هم کنید تا کامپیوترهای سفارشی بسازید.
میخواهید عملکرد ترکیبهای مختلف قطعات را بسنجید و تصمیم میگیرید برنامهی بنچمارک خودتان را بنویسید تا ببینید کامپیوترهایتان در مقایسه با هم چطور عمل میکنند. الگوریتم مشهور «غربال اراتوستن» را انتخاب میکنید؛ الگوریتمی باستانی، اما الگوریتمی که باید کامپیوترهایتان را تا مرز توانشان پیش ببرد.
دستورالعملها
وظیفهی شما این است که برنامهای بنویسید که الگوریتم غربال اراتوستن را پیادهسازی کند و همهی اعداد اول کوچکتر یا مساوی عدد دادهشده را پیدا کند.
عدد اول عددی است بزرگتر از ۱ که فقط بر ۱ و خودش بخشپذیر است.
برای مثال، ۲، ۳، ۵، ۷، ۱۱ و ۱۳ عدد اول هستند.
در مقابل، ۶ عدد اول نیست، چون نهتنها بر ۱ و خودش، بلکه بر ۲ و ۳ هم بخشپذیر است.
برای استفاده از غربال اراتوستن، ابتدا همهی اعداد را از ۲ تا خودِ عدد دادهشده بنویسید.
سپس این مراحل را دنبال کنید:
- عدد بدون علامت بعدی را پیدا کنید (از اعداد علامتدار بگذرید).
این عدد یک عدد اول است.
- همهی مضربهای آن عدد اول را بهعنوان غیر اول علامت بزنید.
این مراحل را تکرار کنید تا همهی اعداد را بررسی کرده باشید.
در پایان، همهی اعداد بدون علامت اول هستند.
غربال اراتوستن مضربهای هر عدد اول را با جمع (افزودن مکرر آن عدد اول) یا ضرب (محاسبهی مستقیم مضربهایش) علامت میزند، نه اینکه هر عدد را از نظر بخشپذیری بررسی کند.
تستها بررسی نمیکنند که شما الگوریتم را پیادهسازی کردهاید؛ فقط بررسی میکنند که اعداد اول درست را به دست آورده باشید.
مثال
فرض کنید میخواهید اعداد اول کوچکتر یا مساوی ۱۰ را پیدا کنید.
-
۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰ را بنویسید و همه را بدون علامت بگذارید.
2 3 4 5 6 7 8 9 10
-
۲ بدون علامت است، پس عدد اول است.
۴، ۶، ۸ و ۱۰ را «غیر اول» علامت بزنید.
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
۳ بدون علامت است، پس عدد اول است.
۶ و ۹ را غیر اول علامت بزنید (علامت زدن ۶ اختیاری است، چون از قبل علامت خورده است).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۴ بهعنوان «غیر اول» علامت خورده است، پس از آن میگذریم.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۵ بدون علامت است، پس عدد اول است.
۱۰ را غیر اول علامت بزنید (اختیاری است، چون از قبل علامت خورده است).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۶ بهعنوان «غیر اول» علامت خورده است، پس از آن میگذریم.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۷ بدون علامت است، پس عدد اول است.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۸ بهعنوان «غیر اول» علامت خورده است، پس از آن میگذریم.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۹ بهعنوان «غیر اول» علامت خورده است، پس از آن میگذریم.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
۱۰ بهعنوان «غیر اول» علامت خورده است، پس متوقف میشویم، چون عدد دیگری برای بررسی نمانده است.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
همهی اعداد را بررسی کردهاید و دیدهاید که ۲، ۳، ۵ و ۷ هنوز بدون علامتاند، یعنی همان اعداد اول کوچکتر یا مساوی ۱۰ هستند.
