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

वृत्तीय अभाज्य संख्याएँ (Circular Primes)

किसी सीमा तक वे अभाज्य संख्याएँ गिनिए जिनके अंकों का हर घुमाव भी अभाज्य हो।

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

  • किसी संख्या के अंक घुमाना
  • हर घुमाव पर शर्त जाँचना
  • शर्त पूरी करने वाली संख्याएँ गिनना

समस्या

किसी संख्या को घुमाने (rotate करने) पर उसका पहला अंक आख़िर में चला जाता है: 197 से 971 बनता है, फिर 719। कोई अभाज्य संख्या वृत्तीय (circular) तब कहलाती है जब उसका हर घुमाव भी अभाज्य हो, इसलिए 197 वृत्तीय है। 2 से limit तक की वृत्तीय अभाज्य संख्याएँ गिनिए। कोई घुमाव limit से बड़ा हो सकता है; फिर भी उसका अभाज्य होना ज़रूरी है।

circular_primes(limit) लिखिए।

इनपुट

limit: जाँची जाने वाली सबसे बड़ी संख्या।

आउटपुट

लौटाइए कि p ≤ limit वाली कितनी अभाज्य संख्याएँ वृत्तीय हैं।

सीमाएँ

1 ≤ limit ≤ 100,000

उदाहरण

उदाहरण 1
इनपुट:
limit = 20

अपेक्षित आउटपुट:
expected = 7
इनपुट:
long long limit = 20;

अपेक्षित आउटपुट:
long long expected = 7;
इनपुट:
long limit = 20;

अपेक्षित आउटपुट:
long expected = 7;

व्याख्या

2, 3, 5, 7, 11, 13 (31 अभाज्य है) और 17 (71 अभाज्य है) वृत्तीय हैं, लेकिन 19 नहीं (91 = 7 × 13): 7।

उदाहरण 2
इनपुट:
limit = 1

अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long limit = 1;

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long limit = 1;

अपेक्षित आउटपुट:
long expected = 0;

व्याख्या

1 तक कोई अभाज्य संख्या नहीं है, इसलिए उत्तर 0 है।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

एक बार घुमाने पर पहला अंक आख़िर में चला जाता है; d अंकों वाली संख्या के d घुमाव होते हैं।

संकेत 2

संख्या को string में बदल लेने से घुमाना आसान हो जाता है।

संकेत 3

घुमाव limit से बड़े हो सकते हैं, इसलिए उनकी अभाज्यता सीधे जाँचिए।

अपेक्षित जटिलता

समय O(limit × d × √(10^d)) trial division के साथ, अतिरिक्त स्थान O(d)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

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

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

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

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

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