Số nguyên tố đầu tiên không nhỏ hơn n (First Prime Not Smaller Than n)

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

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

Đề bài

Với số nguyên dương $n$, tìm số nguyên tố nhỏ nhất $p$ thỏa $p\ge n$. Số nguyên tố là số nguyên lớn hơn 1 có đúng hai ước dương là 1 và chính nó. Nếu $n$ đã nguyên tố thì in $n$; với $n=1$ phải in 2. Không cần sử dụng mảng hay sàng.

Input

Một số nguyên $1\le n\le10^6$.

Output

In số nguyên tố nhỏ nhất không nhỏ hơn $n$.

Subtask

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

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

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

Ví dụ

Ví dụ 1

Input:

14

Output:

17

Giải thích:

Kiểm các ứng viên từ 14 theo thứ tự tăng. Số nguyên tố đầu tiên không nhỏ hơn 14 là 17.

Ví dụ 2

Input:

1

Output:

2

Giải thích:

Kiểm các ứng viên từ 2 theo thứ tự tăng. Số nguyên tố đầu tiên không nhỏ hơn 1 là 2.