मध्यम 0 हल किए गए 0% स्वीकृति

Truncatable Primes

List the primes up to a limit that stay prime as digits are removed from either end.

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

  • Remove digits from either end of a number
  • Test every truncation
  • Collect results in order

समस्या

अनुवाद दिखाएँ

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

उदाहरण

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

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

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

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

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

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

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