문제
3797을 생각해 봅시다. 왼쪽에서 숫자를 지우면 797, 97, 7이 되고, 오른쪽에서 지우면 379, 37, 3이 됩니다. 이 수들은 모두 소수이고 3797도 소수입니다. 이런 소수를 양방향으로 잘라도 소수인 수라고 부르겠습니다. 한 자리 소수는 지울 숫자가 없으므로 포함하지 않습니다. 10부터 limit까지 양방향으로 잘라도 소수인 수를 모두 나열하세요.
truncatable_primes(limit) 함수를 구현하세요.
입력
limit: 확인할 가장 큰 수입니다.
출력
해당하는 소수를 오름차순으로 반환합니다. 하나도 없으면 빈 리스트를 반환합니다.
제약 조건
1 ≤ limit ≤ 100,000
예시
입력:
limit = 40
예상 출력:
expected = [23, 37]
입력:
long long limit = 40;
예상 출력:
std::vector<long long> expected = {23, 37};
입력:
long limit = 40;
예상 출력:
long[] expected = new long[] {23, 37};
설명
23(2, 3)과 37(3, 7)은 조건을 만족합니다. 13은 1이 소수가 아니고, 29는 9가 소수가 아니어서 탈락합니다. 답은 [23, 37]입니다.
입력:
limit = 10
예상 출력:
expected = []
입력:
long long limit = 10;
예상 출력:
std::vector<long long> expected = {};
입력:
long limit = 10;
예상 출력:
long[] expected = new long[] {};
설명
10 미만에는 한 자리 소수만 있고 이들은 포함하지 않으므로 []입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
오른쪽에서 지우는 것은 10으로 나누는 것입니다.
힌트 2
왼쪽에서 지우는 것은 10의 거듭제곱으로 나눈 나머지를 구하는 것입니다.
힌트 3
한 자리가 될 때까지 잘라 낸 모든 수가 소수여야 하고, 원래 수도 소수여야 합니다.
예상 복잡도
시간 O(limit × d × √limit), 추가 공간 O(answer)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.