समस्या
Return all prime numbers from 2 through limit. A prime is an integer greater than 1 divisible only by 1 and itself. Use the sieve idea: keep the next unmarked number and mark its larger multiples as composite. List results in ascending order.
Implement sieve_primes(limit).
Input
limit: The largest number that may be included.
Output
Return the primes in ascending order, or an empty list if none exist.
सीमाएँ
0 ≤ limit ≤ 100,000. The upper bound is inclusive. Output tests verify results, not the exact algorithm used.
उदाहरण
इनपुट:
limit = 12
अपेक्षित आउटपुट:
expected = [2, 3, 5, 7, 11]इनपुट:
long long limit = 12;
अपेक्षित आउटपुट:
std::vector<long long> expected = {2, 3, 5, 7, 11};इनपुट:
long limit = 12;
अपेक्षित आउटपुट:
long[] expected = new long[] {2, 3, 5, 7, 11};व्याख्या
Mark multiples of 2 and 3 as composite. The remaining values up to 12 are 2, 3, 5, 7, and 11.
इनपुट:
limit = 1
अपेक्षित आउटपुट:
expected = []इनपुट:
long long limit = 1;
अपेक्षित आउटपुट:
std::vector<long long> expected = {};इनपुट:
long limit = 1;
अपेक्षित आउटपुट:
long[] expected = new long[] {};व्याख्या
Prime numbers begin at 2, beyond this limit.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर unmarked prime candidate से शुरू करके composites mark करो और limit तक जारी रखो।
संकेत 2
अंत में जो numbers unmarked रहें, वही prime हैं।
संकेत 3
Candidate का square limit से बड़ा हो जाए तो उसके multiples mark करना बंद कर दो।
अपेक्षित जटिलता
समय O(n log log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।