Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Truncatable Primes

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

1 ≤ limit ≤ 100,000

Ví dụ

Ví dụ 1
Đầu vào:
limit = 40

Kết quả mong đợi:
expected = [23, 37]
Đầu vào:
long long limit = 40;

Kết quả mong đợi:
std::vector<long long> expected = {23, 37};
Đầu vào:
long limit = 40;

Kết quả mong đợi:
long[] expected = new long[] {23, 37};

Giải thích

23 (2, 3), 37 (3, 7) both work; 13 fails because 1 is not prime and 29 fails because 9 is not. [23, 37].

Ví dụ 2
Đầu vào:
limit = 10

Kết quả mong đợi:
expected = []
Đầu vào:
long long limit = 10;

Kết quả mong đợi:
std::vector<long long> expected = {};
Đầu vào:
long limit = 10;

Kết quả mong đợi:
long[] expected = new long[] {};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Removing from the right is division by 10.

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.