مقدمه
شما در یک حراجی خانگی، یک جعبهی بزرگ پر از قطعات کامپیوتری درهموبرهم خریدهاید. حالا شروع کردهاید این قطعات را سر هم کنید تا کامپیوترهای سفارشی بسازید.
میخواهید عملکرد ترکیبهای مختلف قطعات را بسنجید و تصمیم میگیرید برنامهی بنچمارک خودتان را بنویسید تا ببینید کامپیوترهایتان در مقایسه با هم چطور عمل میکنند. الگوریتم مشهور «غربال اراتوستن» را انتخاب میکنید؛ الگوریتمی باستانی، اما الگوریتمی که باید کامپیوترهایتان را تا مرز توانشان پیش ببرد.
دستورالعملها
وظیفهی شما این است که برنامهای بنویسید که الگوریتم غربال اراتوستن را پیادهسازی کند تا همهی اعداد اول کوچکتر یا مساوی یک عدد مشخص را پیدا کند.
«عدد اول» عددی بزرگتر از ۱ است که فقط بر ۱ و خودش بخشپذیر است.
برای مثال، ۲، ۳، ۵، ۷، ۱۱ و ۱۳ عدد اول هستند.
در مقابل، ۶ عدد اول نیست، چون نهتنها بر ۱ و خودش، بلکه بر ۲ و ۳ هم بخشپذیر است.
برای استفاده از غربال اراتوستن، ابتدا فهرستی از همهی اعداد بین ۲ و عدد مشخصتان میسازید.
سپس مراحل زیر را تکرار میکنید:
- عدد علامتنخوردهی بعدی را در فهرستتان پیدا کنید (از اعداد علامتخورده رد شوید).
این عدد اول است.
- همهی مضربهای آن عدد اول را به عنوان غیر اول علامت بزنید.
این مراحل را تکرار میکنید تا همهی اعداد فهرستتان را بررسی کنید.
در پایان، همهی اعداد علامتنخورده اول هستند.
تستها بررسی نمیکنند که شما این الگوریتم را پیادهسازی کردهاید؛ فقط بررسی میکنند که فهرست درست اعداد اول را به دست آوردهاید.
برای بررسی اینکه غربال را درست پیادهسازی میکنید، یک تست اول خوب این است که بررسی کنید از عملهای تقسیم یا باقیمانده استفاده نمیکنید.
مثال
فرض کنید میخواهید اعداد اول کوچکتر یا مساوی ۱۰ را پیدا کنید.
- اعداد ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹ و ۱۰ را بنویسید و همه را علامتنخورده بگذارید.
- ۲ علامت نخورده است و بنابراین اول است.
۴، ۶، ۸ و ۱۰ را «غیر اول» علامت بزنید.
- ۳ علامت نخورده است و بنابراین اول است.
۶ و ۹ را غیر اول علامت بزنید (علامت زدن ۶ اختیاری است، چون قبلاً علامت خورده است).
- ۴ به عنوان «غیر اول» علامت خورده است، پس از آن رد میشویم.
- ۵ علامت نخورده است و بنابراین اول است.
۱۰ را غیر اول علامت بزنید (اختیاری است، چون قبلاً علامت خورده است).
- ۶ به عنوان «غیر اول» علامت خورده است، پس از آن رد میشویم.
- ۷ علامت نخورده است و بنابراین اول است.
- ۸ به عنوان «غیر اول» علامت خورده است، پس از آن رد میشویم.
- ۹ به عنوان «غیر اول» علامت خورده است، پس از آن رد میشویم.
- ۱۰ به عنوان «غیر اول» علامت خورده است، پس متوقف میشویم، چون عدد دیگری برای بررسی نمانده است.
همهی اعداد را بررسی کردید و دیدید که ۲، ۳، ۵ و ۷ هنوز علامت نخوردهاند، یعنی همان اعداد اول کوچکتر یا مساوی ۱۰ هستند.
