समस्या
3797 लीजिए। बाईं ओर से अंक हटाने पर 797, 97 और 7 मिलते हैं; दाईं ओर से हटाने पर 379, 37 और 3। ये सभी अभाज्य हैं, और 3797 भी। ऐसी अभाज्य संख्या को दोनों ओर से truncatable कहते हैं। एक अंक वाली अभाज्य संख्याओं में हटाने को कुछ नहीं होता, इसलिए वे नहीं गिनी जातीं। 10 से limit तक की हर दोनों ओर से truncatable अभाज्य संख्या की सूची बनाइए।
truncatable_primes(limit) लिखिए।
इनपुट
limit: जाँची जाने वाली सबसे बड़ी संख्या।
आउटपुट
अभाज्य संख्याओं को बढ़ते क्रम में लौटाइए। अगर कोई न हो तो खाली सूची लौटाइए।
सीमाएँ
1 ≤ limit ≤ 100,000
उदाहरण
इनपुट:
limit = 40
अपेक्षित आउटपुट:
expected = [23, 37]
इनपुट:
long long limit = 40;
अपेक्षित आउटपुट:
std::vector<long long> expected = {23, 37};
इनपुट:
long limit = 40;
अपेक्षित आउटपुट:
long[] expected = new long[] {23, 37};
व्याख्या
23 (2, 3) और 37 (3, 7) दोनों शर्त पूरी करते हैं; 13 नहीं, क्योंकि 1 अभाज्य नहीं है, और 29 नहीं, क्योंकि 9 अभाज्य नहीं है। [23, 37]।
इनपुट:
limit = 10
अपेक्षित आउटपुट:
expected = []
इनपुट:
long long limit = 10;
अपेक्षित आउटपुट:
std::vector<long long> expected = {};
इनपुट:
long limit = 10;
अपेक्षित आउटपुट:
long[] expected = new long[] {};
व्याख्या
10 से नीचे सिर्फ़ एक अंक वाली अभाज्य संख्याएँ हैं और वे नहीं गिनी जातीं: []।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
दाईं ओर से अंक हटाना 10 से भाग देना है।
संकेत 2
बाईं ओर से अंक हटाना 10 की किसी घात से modulo लेना है।
संकेत 3
एक अंक तक की हर कटी हुई संख्या अभाज्य होनी चाहिए, और खुद संख्या भी।
अपेक्षित जटिलता
समय O(limit × d × √limit), अतिरिक्त स्थान O(answer) (उत्तर का आकार)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।