समस्या
Take 3797. Removing digits from the left gives 797, 97 and 7; removing them from the right gives 379, 37 and 3. All of them are prime, and so is 3797. Call such a prime two-sided truncatable. One-digit primes have nothing to remove and do not count. List every two-sided truncatable prime from 10 to limit.
Implement truncatable_primes(limit).
Input
limit: The largest number to check.
Output
Return the primes in increasing order. Return an empty list if there are none.
सीमाएँ
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) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [23, 37].
इनपुट:
limit = 10
अपेक्षित आउटपुट:
expected = []
इनपुट:
long long limit = 10;
अपेक्षित आउटपुट:
std::vector<long long> expected = {};
इनपुट:
long limit = 10;
अपेक्षित आउटपुट:
long[] expected = new long[] {};
व्याख्या
Only one-digit primes are below 10 and they do not count: [].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Removing from the right is division by 10.
संकेत 2
Removing from the left is taking the remainder modulo a power of 10.
संकेत 3
Every truncation down to a single digit must be prime, and so must the number.
अपेक्षित जटिलता
O(limit × d × √limit) time, O(answer) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।