सभी चुनौतियाँ
आसान 0 हल किए गए 0% स्वीकृति

किसी रेंज में अभाज्य संख्याओं की गिनती

दो सीमाओं के बीच, दोनों को शामिल करके, कितनी अभाज्य संख्याएँ हैं, यह गिनिए।

आप क्या सीखेंगे

  • Sieve से भाज्य संख्याओं पर निशान लगाना
  • किसी रेंज के भीतर चिह्नित मान गिनना
  • खाली रेंज और 0 व 1 जैसी संख्याएँ संभालना

समस्या

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

उदाहरण

उदाहरण 1
इनपुट:
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 है।

उदाहरण 2
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।