Đề bài
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ụ
Đầ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.
Đầ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.