TRỪ HOẶC CHIA CHO MỘT SỐ NGUYÊN DƯƠNG 𝑛. TẠI MỖI BƯỚC BẠN CÓ TH...

Bài 2. Trừ hoặc chia

Cho một số nguyên dương 𝑛. Tại mỗi bước bạn có thể biến đổi 𝑛 theo một trong hai cách: • Chia số 𝑛 cho một ước dương thực sự của nó (Ước dương thực sự của 𝑛 là một số nguyên dương 𝑑 < 𝑛 sao cho 𝑛 chia hết cho 𝑑) • Trừ 𝑛 đi một đơn vị Yêu cầu: Hãy xác định số bước biến đổi ít nhất để có thể biến đổi 𝑛 thành số 1 Dữ liệu: Vào từ file văn bản SUBORDIV.INP • Dòng 1: Chứa số nguyên dương 𝑇 (1 ≤ 𝑇 ≤ 100) là số bộ dữ liệu. • Dòng 2...𝑇 + 1: Mỗi dòng chứa một số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 10

⁹

) Kết quả: Ghi ra file văn bản SUBORDIV.OUT Gồm 𝑇 dòng, dòng thứ 𝑖 chứa một số nguyên là số phép biến đổi ít nhất cần thực hiện để đưa số nguyên dương 𝑛 trong dòng 𝑖 + 1 của file dữ liệu trở thành số 1 (𝑖 = 1,2, … , 𝑇) Trang: 1 Ví dụ:

SUBORDIV.INP

SUBORDIV.OUT

0

6

1

2

3

4

9

Giải thích: 1 2→1 3→2→1 4→2→1 6→2→1 9→3→2→1