समस्या
1 से 100 तक कितनी अभाज्य संख्याएँ हैं? और 50 से 60 तक? ऐसी अभाज्य संख्याएँ p गिनिए जिनके लिए low ≤ p ≤ high हो। याद रखिए कि 0 और 1 अभाज्य नहीं हैं। high तक का sieve यह जल्दी बता देता है।
count_primes_in_range(low, high) लिखिए।
इनपुट
low: निचली सीमा, जो शामिल है।
high: ऊपरी सीमा, जो शामिल है।
आउटपुट
रेंज में आने वाली अभाज्य संख्याओं की गिनती लौटाइए। अगर low > high हो तो रेंज खाली है और उत्तर 0 है।
सीमाएँ
0 ≤ low ≤ 1,000,000
0 ≤ high ≤ 1,000,000
उदाहरण
इनपुट:
low = 1
high = 100
अपेक्षित आउटपुट:
expected = 25
इनपुट:
long long low = 1;
long long high = 100;
अपेक्षित आउटपुट:
long long expected = 25;
इनपुट:
long low = 1;
long high = 100;
अपेक्षित आउटपुट:
long expected = 25;
व्याख्या
100 तक 25 अभाज्य संख्याएँ हैं (2, 3, 5, … 97), इसलिए उत्तर 25 है।
इनपुट:
low = 50
high = 60
अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long low = 50;
long long high = 60;
अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long low = 50;
long high = 60;
अपेक्षित आउटपुट:
long expected = 2;
व्याख्या
50 और 60 के बीच सिर्फ़ 53 और 59 अभाज्य हैं, इसलिए उत्तर 2 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
high तक sieve बनाइए, और हर अभाज्य संख्या के गुणजों को उसके वर्ग से शुरू करके काटते जाइए।
संकेत 2
फिर low से high तक उन संख्याओं को गिनिए जो अब भी अभाज्य के रूप में चिह्नित हैं।
संकेत 3
अगर low, high से बड़ा है, तो कुछ भी गणना करने की ज़रूरत नहीं।
अपेक्षित जटिलता
समय O(high log log high), अतिरिक्त स्थान O(high)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।