समस्या
किसी संख्या को घुमाने (rotate करने) पर उसका पहला अंक आख़िर में चला जाता है: 197 से 971 बनता है, फिर 719। कोई अभाज्य संख्या वृत्तीय (circular) तब कहलाती है जब उसका हर घुमाव भी अभाज्य हो, इसलिए 197 वृत्तीय है। 2 से limit तक की वृत्तीय अभाज्य संख्याएँ गिनिए। कोई घुमाव limit से बड़ा हो सकता है; फिर भी उसका अभाज्य होना ज़रूरी है।
circular_primes(limit) लिखिए।
इनपुट
limit: जाँची जाने वाली सबसे बड़ी संख्या।
आउटपुट
लौटाइए कि p ≤ limit वाली कितनी अभाज्य संख्याएँ वृत्तीय हैं।
सीमाएँ
1 ≤ limit ≤ 100,000
उदाहरण
इनपुट:
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।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।