Cho một số nguyên dương n (có thể rất lớn), hãy kiểm tra xem n có phải là số nguyên tố hay không.

Giới hạn

• 2 ≤ n ≤ 10⁹

Input

• Một số nguyên dương n duy nhất trên một dòng.

Output

• In ra YES nếu n là số nguyên tố.
• In ra NO nếu n không phải là số nguyên tố.

Ví dụ

Gợi ý

- Mọi số nguyên tố lớn hơn 3 đều có dạng 6k ± 1.
- Không phải mọi số dạng 6k ± 1 đều là nguyên tố.
- Vì thế, bạn nên dùng vòng lặp kiểm tra ước từ 5 đến √n, tăng 6 mỗi lần: i = 5, i += 6, và kiểm tra n % i == 0 hoặc n % (i + 2) == 0.