모든 챌린지
보통 0명 해결 정답률 0%

잘라도 소수인 수

한계값 이하의 소수 중 양쪽 끝에서 숫자를 지워 나가도 계속 소수인 수를 나열합니다.

배우게 될 내용

  • 수의 양쪽 끝에서 숫자를 지울 수 있다
  • 잘라낸 모든 수를 검사할 수 있다
  • 결과를 순서대로 모을 수 있다

문제

원문 보기 (영어)

3797을 생각해 봅시다. 왼쪽에서 숫자를 지우면 797, 97, 7이 되고, 오른쪽에서 지우면 379, 37, 3이 됩니다. 이 수들은 모두 소수이고 3797도 소수입니다. 이런 소수를 양방향으로 잘라도 소수인 수라고 부르겠습니다. 한 자리 소수는 지울 숫자가 없으므로 포함하지 않습니다. 10부터 limit까지 양방향으로 잘라도 소수인 수를 모두 나열하세요.

truncatable_primes(limit) 함수를 구현하세요.

입력

limit: 확인할 가장 큰 수입니다.

출력

해당하는 소수를 오름차순으로 반환합니다. 하나도 없으면 빈 리스트를 반환합니다.

제약 조건

1 ≤ limit ≤ 100,000

예시

예시 1
입력:
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]입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.