Ước lớn nhất nhỏ hơn n (Largest Proper Divisor)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n\ge2$. Tìm ước dương lớn nhất của $n$ nhưng nhỏ hơn chính $n$. Số 1 luôn là ứng viên, kể cả khi $n$ nguyên tố. Ví dụ $n=12$ có các ước dương nhỏ hơn 12 là $1,2,3,4,6$, nên đáp án là 6.

Input

Một số nguyên $n$ với $2\le n\le10^6$.

Output

In một số nguyên là ước dương lớn nhất khác $n$.

Subtask

• Subtask 1 (20%): $2\le n\le 50$.

• Subtask 2 (30%): $2\le n\le 10000$.

• Subtask 3 (50%): $2\le n\le 1000000$.

Ví dụ

Ví dụ 1

Input:

12

Output:

6

Giải thích:

Các ước thực sự của 12 gồm 1, 2, 3, 4, 6. Ước lớn nhất là 6.

Ví dụ 2

Input:

13

Output:

1

Giải thích:

Các ước thực sự của 13 gồm 1. Ước lớn nhất là 1.