happySequence2

Phiên bản nâng cấp hơn của happySequence1

Nhắc lại:

“Tại vương quốc Ba Tư xa xưa, người ta thường tổ chức các cuộc thi tìm dãy số hạnh phúc: Các chàng trai, cô gái thông minh trong thời gian ngắn nhất phải tìm ra được một dãy số hạnh phúc có nhiều phần tử nhất.

Dãy số nguyên dương a1,a2,...,ak được gọi là hạnh phúc nếu nó thoả mãn các điều kiện sau:

• Dãy trên là một dãy giảm dần.
• Với mọi i, ai hoặc là số nguyên tố, hoặc phải là ước của một trong các số a1,a2,...,ai-1.”

Vòng 1 của cuộc thi đã kết thúc. Ở vòng 2 này, người chủ trì vẫn đưa ra một số nguyên n, nhưng phạm vi lớn hơn. Người tìm được số lượng phần tử của dãy số hạnh phúc dài nhất với phần tử đầu tiên là n sẽ là người giành chiến thắng. Lần này lại phải tiếp tục nhờ sự trợ giúp của bạn rồi!

Ví dụ:

• Với n = 4, output happySequence2(n) = 4. Giải thích: dãy số hạnh phúc dài nhất thỏa mãn là [4,3,2,1] có 4 phần tử.
• Với n = 16, output happySequence2(n) = 10. Giải thích: dãy số hạnh phúc dài nhất thỏa mãn là [16,13,11,8,7,5,4,3,2,1] có 10 phần tử. 

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s (C++), 3s (Java, C#), 4s (Python, JavaScript, Go)
• [Đầu vào] integer n

   0 ≤ n ≤ 5×106 

• [Đầu ra] integer

    Số lượng phần tử của dãy số hạnh phúc dài nhất với phần tử đầu tiên là n. Nếu không tồn tại dãy thỏa mãn thì trả về 0.