Beauty | Câu 2 - đề HSG tin 11 | Nghệ An năm 2015 - 2016

Bài 2. (6 điểm)                              BEAUTY
                 Một số được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.
 Ví dụ, 12 là một số đẹp vì 1² + 2² = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.
Yêu cầu: Cho số nguyên N (1 ≤ N ≤ 10⁶). Hãy tìm số đẹp thứ N.
Dữ liệu: Vào từ file BEAUTY.INP
Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên N.
Kết quả: Ghi ra file BEAUTY.OUT
Mỗi test đưa ra trên một dòng là kết quả số đẹp tìm được tương ứng của mỗi test từ file dữ liệu vào.
Ví dụ:

BEAUTY.INP	BEAUTY.OUT
1 6	11 23

Lời giải:

Vì bài toán yêu cầu tìm số đẹp thứ n nên phải kiểm tra tính nguyên tố của n số, vì vậy ta sẽ sử dụng thuật toán sàng nguyên tố Eratosthenes. Và trong bài này chúng ta chỉ sàng đến số 811, bởi chúng ta biết rằng nếu số cần xét là có 10 chữ số 9 thì tổng bình phương các chữ số của nó cũng chỉ là 810. Do đó những số đẹp trong bài này chắc chắn sẽ có tổng bình phương các chữ số nhỏ hơn 810 thôi, thực tế thì số đẹp thứ 10⁶ cũng chỉ có 7 chữ số thôi.

Sàng nguyên tố Eratosthenes:

s=[1]*811
s[0],s[1]=0,0
for i in range(2,int(811**0.5)+1):
    for j in range(i*i,811,i):
        s[j]=0

Đầu tiên ta xem các số từ 0 đến 810 đều là số nguyên tố: s = [1]*811. Tiếp theo vì số 0 và số 1 không phải là số nguyên tố nên ta gán lại s[],s[1] = 0,0 . Từ số 2 trở đi ta cho i chạy từ 2 đến phần nguyên của căn bậc hai 811 +1: for i in range(2,int(811**0.5)+1):. Sau đó dùng vòng lặp j để loại các số là bội của i (hay nói cách khác i là ước của j nên j không phải là số nguyên tố:for j in range(i*i,811,i): s[j]=0. Sau khi sàng như vậy thì ta sẽ có nếu s[a] = 1 thì a là số nguyên tố. 

Tiếp theo ta xây dựng một hàm tìm số đẹp thứ n như sau:

def sodep(n):
    if n == 1:
        return 11
    j,i = 1,11
    while j < n:
        i += 1
        a,b = str(i),0
        for x in range(len(a)):
            b += (int(a[x]))**2
        if s[b]==1:
            j += 1
            kq = i
    return kq

Chú ý: Số đẹp đầu tiên là số 11. i là số đang xét, và ta dùng biến a đển chuyển i về kiểu chuỗi để xử lý. Nếu i là số đẹp thì tăng j lên 1 (Số đẹp thứ j sẽ là i). Sau khi xây dựng hàm thì chỉ việc gọi hàm sodep(n) là ta có kết quả số đẹp thứ n.

Code trọn vẹn:

s=[1]*811
s[0],s[1]=0,0
for i in range(2,int(811**0.5)+1):
    for j in range(i*i,811,i):
        s[j]=0
def sodep(n):
    if n == 1:
        return 11
    j,i = 1,11
    while j < n:
        i += 1
        a,b = str(i),0
        for x in range(len(a)):
            b += (int(a[x]))**2
        if s[b]==1:
            j += 1
            kq = i
    return kq
with open("Beauty.INP", "r") as f:
    n = int(f.readline().strip())

with open("BEAUTY.OUT", "w") as f:
    f.write(str(sodep(n)))          
  

Các test của bài này admin gửi các bạn ở cuối bài viết: