Số nguyên tố đối xứng

[Griff_Fin]

Một số nguyên tố p được gọi là số nguyên tố đối xứng nếu mang biểu diễn thập phân của nó viết theo thứ tự ngược lại, ta vẫn được một số nguyên tố. Ví dụ: 79,97,991,1999859 là những số nguyên tố đối xứng.

Yêu cầu: Liệt kê các số nguyên tố đối xứng trong phạm vi từ 1 tới n theo thứ tự tăng dần

Input

• Gồm một số nguyên dương n≤2000000.

Output

• Ghi các số nguyên tố tìm được theo thứ tự tăng dần cách nhau bởi dấu cách.

Example

100

2 3 5 7 11 13 17 31 37 71 73 79 97

Có cách nào tối ưu để chạy sub lớn không

[noname00 (HK boy)]

Bạn dùng sàng Eratosthenes để liệt kê các số nguyên tố từ 1 đến 2 triệu (có 148933 số như vậy).

Sau đó cứ duyệt for bình thường.

# giả sử primes là danh sách các số nguyên tố nhỏ hơn 2 triệu
for p in primes:
    rev_p = đảo ngược n
    if p <= n and (rev_p nằm trong p):
        print(p, end=' ')

Bước kiểm tra rev_p nằm trong p hay không thì bạn có thể dùng binary search nhé.