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

Circular Primes

Count the primes up to a limit whose every digit rotation is also prime.

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

  • Rotate the digits of a number
  • Check a condition on every rotation
  • Count numbers that pass

समस्या

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

Rotating a number moves its first digit to the end: 197 becomes 971, then 719. A prime is circular when every rotation is prime too, so 197 is circular. Count the circular primes from 2 to limit. A rotation may be larger than the limit; it still has to be prime.

Implement circular_primes(limit).

Input

limit: The largest number to check.

Output

Return how many primes p ≤ limit are circular.

सीमाएँ

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 is prime) and 17 (71 is prime) are circular, but 19 is not (91 = 7 × 13): 7.

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

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

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

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

व्याख्या

There are no primes up to 1, so the answer is 0.

कैसे हल करें

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

संकेत 1

Rotating once moves the first digit to the end; a d-digit number has d rotations.

संकेत 2

Turning the number into a string makes rotation easy.

संकेत 3

Rotations can be bigger than the limit, so test them for primality directly.

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

O(limit × d × √(10^d)) time with trial division, O(d) extra space

संदर्भ

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

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

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

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

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

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