Medium 0 solved 0% acceptance

Circular Primes

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

What you'll learn

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

Problem

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.

Constraints

1 ≤ limit ≤ 100,000

Examples

Example 1
Input:
limit = 20

Expected output:
expected = 7
Input:
long long limit = 20;

Expected output:
long long expected = 7;
Input:
long limit = 20;

Expected output:
long expected = 7;

Explanation

2, 3, 5, 7, 11, 13 (31 is prime) and 17 (71 is prime) are circular, but 19 is not (91 = 7 × 13): 7.

Example 2
Input:
limit = 1

Expected output:
expected = 0
Input:
long long limit = 1;

Expected output:
long long expected = 0;
Input:
long limit = 1;

Expected output:
long expected = 0;

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

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

Hint 2

Turning the number into a string makes rotation easy.

Hint 3

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

Expected complexity

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

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.