Remarkable Primes
InterviewTime limit2sMemory limit4 MB
Given N, output all N-digit primes whose every left-hand prefix (1 to N digits) is also prime, in ascending order.
- Level
Medium4 of 10
- Topics
- Backtracking, Math, Number theory
- Solved
- No attempts yet
Problem
Subin loves prime numbers and enjoys exploring them. Recently, one number caught her attention: 7331.
The number 7331 is prime. More surprisingly, 733, 73, and 7 are also prime. In other words, every prefix formed by taking the first 1, 2, 3, and 4 digits from the left is prime. Subin calls such a number a remarkable prime.
Given N, find every N-digit remarkable prime.
Input
The first line contains an integer N (1 ≤ N ≤ 8).
Output
Print all N-digit remarkable primes in ascending order, one per line.