백준 2023 신기한 소수

0이 왜 거기서 나와...

 

왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이므로
최초 왼쪽 한자리에 소수가 가능한 2,3,5,7로 시작한다. (x 라고 설정)
그 다음에는 x * 10 + i가 소수인지 판정하면 되는데
짝수 및 5는 나누어짐으로 i는 1,3,7,9가 대상이 된다.
소수로 판정이 나면 위 작업을 해당 숫자가 N자리가 될 때 까지 반복한다.

 

n=int(input())
r=[]  # result, 결과 저장용

def f(x):# 재귀함수
 if x//(10**(n-1)):r.append(x);return #숫자의 자리수가 n이면 결과 리스트에 추가하고 리턴

for i in[1,3,7,9]: # 위에서  x * 10 + i가 소수인지 판정시 i에 해당하는 숫자
  t=x*10+i  # 자리수를 하나 늘림. 
  p=1 # 소수 플래그

  for j in range(2,int(t**.5)+1):
   if t%j<1:p=0;break # 소수가 아님
  
  if p:f(t) # 소수이면 다시 호출

for i in[2,3,5,7]:f(i) # 맨 좌측 1 자리 1자리수 소수로 출발

print(*r)

 

https://www.acmicpc.net/problem/2023