All challenges
Medium 0 solved 0% acceptance

Truncatable Primes

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

What you'll learn

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

Problem

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.

Constraints

1 ≤ limit ≤ 100,000

Examples

Example 1
Input:
limit = 40

Expected output:
expected = [23, 37]
Input:
long long limit = 40;

Expected output:
std::vector<long long> expected = {23, 37};
Input:
long limit = 40;

Expected output:
long[] expected = new long[] {23, 37};

Explanation

23 (2, 3), 37 (3, 7) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [23, 37].

Example 2
Input:
limit = 10

Expected output:
expected = []
Input:
long long limit = 10;

Expected output:
std::vector<long long> expected = {};
Input:
long limit = 10;

Expected output:
long[] expected = new long[] {};

Explanation

Only one-digit primes are below 10 and they do not count: [].

How to approach it

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

Hint 1

Removing from the right is division by 10.

Hint 2

Removing from the left is taking the remainder modulo a power of 10.

Hint 3

Every truncation down to a single digit must be prime, and so must the number.

Expected complexity

O(limit × d × √limit) time, O(answer) 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.