Số nguyên tố

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 KT Số nguyên tố 100 (p) 1.0s 1023M
2 Đếm số nguyên tố nhỏ hơn n 100 (p) 1.0s 256M
3 Tìm số nguyên tố 100 (p) 1.0s 640M

1. KT Số nguyên tố

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong ngày thực tập đầu tiên, thầy Hải có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\), hãy kiểm tra \(n\) có phải là số nguyên tố hay không?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

  • Gồm một dòng duy nhất là số nguyên \(n (|n| \le 10^{12})\)

Output:

  • In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO.

Example

Test 1

Input 
9
Output 
NO

Test 1

Input 
7
Output 
YES

2. Đếm số nguyên tố nhỏ hơn n

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên \(n\), đếm xem có bao nhiêu số nguyên tố \(\le n\).

Input

  • Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 10^7\)).

Output

  • In ra một số nguyên duy nhất là số lượng số nguyên tố nhỏ hơn hoặc bằng \(n\).

Example

Test 1

Input 
10
Output 
4
Note

Các số nguyên tố nhỏ hơn hoặc bằng \(10\) là: \(2, 3, 5, 7\). Tổng cộng có \(4\) số.

3. Tìm số nguyên tố

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

  • Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

  • Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

Test 1

Input 
1 10
Output 
2
3
5
7