Kiểm tra số nguyên tố

Bối cảnh

Một hệ thống đánh số chỉ chấp nhận các mã nguyên tố. Mỗi mã cần được kiểm tra nhanh và chính xác.

Điểm khó của bài không nằm ở cú pháp mà ở các case nhỏ: 0, 1, 2, số chẵn và số chính phương.

Yêu cầu

1. Đọc số nguyên n.
2. In PRIME nếu n là số nguyên tố, ngược lại in NOT PRIME.
3. Chỉ thử ước đến khi i*i > n.

Yêu cầu tổ chức code

Tạo hàm bool isPrime(long long n).

Lưu ý: Online Judge chủ yếu kiểm tra tính đúng của output. Yêu cầu tổ chức code được dùng để rèn đúng kỹ năng của buổi học và sẽ được giảng viên quan sát khi chữa bài.

Input

Một số nguyên n.

Output

PRIME hoặc NOT PRIME.

Ràng buộc

-10^12 ≤ n ≤ 10^12.

Ví dụ 1

Input

29

Output

PRIME

Giải thích

29 lớn hơn 1 và không có ước nào từ 2 đến √29, nên 29 là số nguyên tố. Output là PRIME.

Ví dụ 2

Input

1

Output

NOT PRIME

Giải thích

1 không phải số nguyên tố vì số nguyên tố phải lớn hơn 1. Output là NOT PRIME.

Thông tin học tập

• Module: M02
• Buổi: B07
• Loại bài: LAB
• Độ khó: Easy
• Concepts: functions, primality testing, square-root optimization, boundary cases
• Giới hạn kiến thức: B01-B07
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100