समस्या
एक अभाज्य संख्या वह पूर्णांक है जो 1 और स्वयं के अलावा किसी अन्य संख्या से विभाजित नहीं होती और 1 से बड़ी होती है। सीमा से छोटी प्रत्येक अभाज्य संख्या को जोड़ें। यदि सीमा स्वयं अभाज्य है, तो भी उसे शामिल न करें।
prime_sum(limit) को लागू करें।
इनपुट
limit: अपर सीमा (exclusive)।
आउटपुट
योग्य अभाज्य संख्याओं का योग लौटाएँ, या यदि कोई नहीं है तो 0 लौटाएँ।
सीमाएँ
0 ≤ limit ≤ 2,000,000। योग को signed 64-bit integer के रूप में लौटाएँ।
उदाहरण
इनपुट:
limit = 12
अपेक्षित आउटपुट:
expected = 28इनपुट:
long long limit = 12;
अपेक्षित आउटपुट:
long long expected = 28;इनपुट:
long limit = 12;
अपेक्षित आउटपुट:
long expected = 28;व्याख्या
12 से कम अभाज्य संख्याएँ हैं: 2, 3, 5, 7, और 11; इनका योग 28 है।
इनपुट:
limit = 2
अपेक्षित आउटपुट:
expected = 0इनपुट:
long long limit = 2;
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long limit = 2;
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
2 से कम कोई भी अभाज्य संख्या नहीं है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Main cost primes efficiently ढूँढने में है; हर number के लिए naive divisibility checks बहुत slow होंगे।
संकेत 2
Composites mark करने के लिए sieve-like approach use करो, फिर जो unmarked रहें और limit से छोटे हों उन्हें add करो।
संकेत 3
Limit खुद include नहीं होती, even if वह prime हो, और छोटे limits से कुछ भी contribute नहीं हो सकता।
अपेक्षित जटिलता
समय O(limit log log limit), अतिरिक्त स्थान O(limit)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।