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

Số nguyên tố vòng

Đếm các số nguyên tố không vượt quá giới hạn mà mọi phép xoay vòng chữ số đều cho số nguyên tố.

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

  • Xoay vòng các chữ số của một số
  • Kiểm tra điều kiện trên mọi phép xoay
  • Đếm các số thỏa mãn

Đề bài

Xem bản gốc (English)

Xoay vòng một số nghĩa là chuyển chữ số đầu tiên xuống cuối: 197 thành 971, rồi thành 719. Một số nguyên tố được gọi là số nguyên tố vòng nếu mọi phép xoay của nó cũng là số nguyên tố, nên 197 là số nguyên tố vòng. Hãy đếm các số nguyên tố vòng từ 2 đến limit. Một phép xoay có thể lớn hơn giới hạn, nhưng vẫn phải là số nguyên tố.

Hãy viết circular_primes(limit).

Đầu vào

limit: Số lớn nhất cần kiểm tra.

Đầu ra

Trả về số lượng số nguyên tố p ≤ limit là số nguyên tố vòng.

Ràng buộc

1 ≤ limit ≤ 100,000

Ví dụ

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

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

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

Kết quả mong đợi:
long expected = 7;

Giải thích

2, 3, 5, 7, 11, 13 (31 là số nguyên tố) và 17 (71 là số nguyên tố) đều là số nguyên tố vòng, còn 19 thì không (91 = 7 × 13): 7.

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

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

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

Kết quả mong đợi:
long expected = 0;

Giải thích

Không có số nguyên tố nào nhỏ hơn hoặc bằng 1, nên đáp án là 0.

Hướng tiếp cận

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

Gợi ý 1

Xoay một lần là chuyển chữ số đầu xuống cuối; một số có d chữ số có d phép xoay.

Gợi ý 2

Đổi số thành chuỗi sẽ giúp xoay dễ dàng.

Gợi ý 3

Phép xoay có thể lớn hơn giới hạn, nên hãy kiểm tra tính nguyên tố trực tiếp.

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

thời gian O(limit × d × √(10^d)) với phép chia thử, bộ nhớ phụ O(d)

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.