신기한 소수
면접 대비시간 제한2초메모리 제한4 MB
N이 주어질 때, 앞에서부터 1자리부터 N자리까지의 모든 접두사가 소수인 N자리 소수를 오름차순으로 출력합니다.
문제
수빈이는 소수를 가장 좋아하고, 소수를 살펴보며 노는 것을 즐긴다. 요즘 수빈이가 특히 관심을 가진 수는 7331이다.
7331은 소수이다. 더 신기하게도 733, 73, 7도 모두 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리로 잘라 만든 모든 접두 수가 소수이다. 수빈이는 이런 수를 신기한 소수라고 부른다.
정수 N이 주어졌을 때, N자리 신기한 소수를 모두 찾아보자.
입력
첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 8)
출력
N자리 신기한 소수를 오름차순으로 한 줄에 하나씩 출력한다.