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

Truncatable Primes

List the primes up to a limit that stay prime as digits are removed from either end.

배우게 될 내용

  • Remove digits from either end of a number
  • Test every truncation
  • Collect results in order

문제

번역본 보기

Take 3797. Removing digits from the left gives 797, 97 and 7; removing them from the right gives 379, 37 and 3. All of them are prime, and so is 3797. Call such a prime two-sided truncatable. One-digit primes have nothing to remove and do not count. List every two-sided truncatable prime from 10 to limit.

Implement truncatable_primes(limit).

Input

limit: The largest number to check.

Output

Return the primes in increasing order. Return an empty list if there are none.

제약 조건

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) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [23, 37].

예시 2
입력:
limit = 10

예상 출력:
expected = []
입력:
long long limit = 10;

예상 출력:
std::vector<long long> expected = {};
입력:
long limit = 10;

예상 출력:
long[] expected = new long[] {};

설명

Only one-digit primes are below 10 and they do not count: [].

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Removing from the right is division by 10.

힌트 2

Removing from the left is taking the remainder modulo a power of 10.

힌트 3

Every truncation down to a single digit must be prime, and so must the number.

예상 복잡도

O(limit × d × √limit) time, O(answer) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

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

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

다른 사람의 풀이 보기

커뮤니티 솔루션

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