Tìm số có tổng các chữ số của nó bằng tổng các chữ số của các thừa số nguyên tố của chính nó

[An_Nguyen (An Nguyễn)]

Mọi người giúp e thuật toán bài này vơi ạ!

Một số nguyên dương M được gọi là một số đặc biệt nếu nó thỏa mãn: Tổng các chữ số của M bằng tổng các chữ số của các thừa số nguyên tố là tích của M. Chẳng hạn như số 4937775 là một số đặc biệt vì:
4937775 = 3 . 5 . 5 . 65837
Ta có: 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42
Và: 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42
Yêu cầu: Cho trước một số nguyên dương N. Tìm số đặc biệt nhỏ nhất lớn hơn N.
Dữ liệu vào: Từ file văn bản SODB.INP
Gồm duy nhất 1 dòng là 1 số nguyên dương N (N< 10^9)
Kết quả: Ghi ra file văn bản SODB.OUT
Gồm duy nhất 1 dòng là 1 số đặc biệt nhỏ nhất lớn hơn N
Ví dụ:

SODB.INP	SODB.OUT
4937770	4937775

Về cơ bản thì bài này có thể chạy trâu được, nhưng mà như thế đối với các test to thì sẽ bị quá thời gian, mọi người giúp e xem có cách nào chạy nhanh với ah!!! E cảm ơn!!!

[noname00 (HK boy)]

sẽ bị quá thời gian

Tức là bạn chưa nộp code chạy trâu à?

Chạy trâu cũng có 5 7 kiểu, không phải cứ trâu là chết time.

[tntxtnt]

https://oeis.org/A006753

There are 248483 7-digit Smith numbers

số này tương đối dễ tìm mà, duyệt trâu sao lại quá thời gian :V Em chia tìm thừa số nguyên tố tới căn của số đó là được.

[rogp10]

Bạn nhớ chia xuống N qua mỗi thừa số là pass thôi phân tích thừa số là vậy.