1010: 접두 소수

Link : judge.koreatech.ac.kr/problem.php?id=1010

---

1. 문제

• 숫자 "2333"의 경우 접두 숫자인 "2", "23", "233", "2333" 이 모두 소수입니다.
  길이 n이 주어졌을 때 길이 n에 해당하는 모든 접두 소수를 출력해주세요.

 

---

2. 문제의 조건

• 1 <= n <= 8 (접두소수의 길이)

 

---

3. 문제 접근

• 시간 복잡도
  
  길이가 8일경우 10,000,000 자리가 되면서 최소환 O(N^1.1428) 안에 해결해야한다고 생각하였습니다.
  
  
  
• 아이디어
  
  소수판별은 기본적으로 O(N^2)을 갖게 됩니다. 하지만 소수의 성질을 이용하면 O(sqrt(N))까지 줄일 수 있다는 것을 알게 되었습니다.
  
  접두소수는 맨 앞자리부터 n까지의 길이가 모두 "소수"가 되어야합니다. 결국 맨앞자리 부터 "소수"가 되야 하므로 맨앞자리에 올 수 있는 숫자는 [2, 3, 5, 7]입니다. 그 후 중간부터는 짝수가 들어가게 된다면 2로 나누어 떨어지므로 2의 배수가 되면 안되므로 조건을 줄여줍니다. [1, 3, 5, 7, 9]가 남는데 5도 5로 항상 나뉘어지므로 [1, 3, 7, 9]가 남게 됩니다. 즉 첫수와 끝수는 [2, 3, 5, 7]로 이루어져야만 하고 중간의 수들은 [1, 3, 7, 9]로 이루어져야합니다. 그리고 저는 어떠한 규칙으로 수를 만드는 것은 대부분 재귀를 이용합니다.
  
  재귀의 시간복잡도는 아직 파악하지 못하였습니다. @ + sqrt(N)이 될 것 같습니다.

 

 

 

---

4. 풀이 방법

• 소수를 판별하는 함수를 작성합니다.
• 규칙에 따라 첫, 끝점이 [2, 3, 5, 7]인 숫자와 중간점이 [1, 3, 7, 9]인 숫자를 만들어주는 재귀를 작성합니다.
  (주의 : n이 5로 주어질 경우 만약 n=>2 [2, 1]단계에서 21은 소수가 아니므로 [2 1 1]로 탐색하는 것이 아닌 바로 [2, 3]으로 넘어가시면 됩니다)
• 길이가 n만큼 채워졌을경우 최종적으로 비교하고 소수가맞으면 출력합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/17

 

---

 

cjw.git@gmail.com

 

소수의 성질 출처 : jm-park.github.io/algorithm/2018/08/06/Prime-Number(%EC%86%8C%EC%88%98)-%ED%8C%90%EB%B3%84%EB%B2%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.html