Cặp nguyên tố sinh đôi

Bối cảnh

Hai số nguyên tố được gọi là nguyên tố sinh đôi nếu chúng cách nhau đúng 2, ví dụ (3,5), (5,7), (11,13).

Cho giới hạn N, hãy đếm bao nhiêu cặp (p, p+2) mà cả hai đều nguyên tố và p+2 ≤ N.

Yêu cầu

1. Đọc số nguyên N.
2. Duyệt p từ 2 đến N-2.
3. Nếu isPrime(p) và isPrime(p+2) cùng đúng, tăng bộ đếm.
4. In số cặp.

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

Bắt buộc dùng hàm isPrime; không dùng mảng/sàng ở bài này.

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

Một số nguyên là số cặp nguyên tố sinh đôi không vượt quá N.

Ràng buộc

2 ≤ N ≤ 10^5.

Ví dụ 1

Input

5

Output

1

Giải thích

Các cặp không vượt quá 5 là (3,5), nên có 1 cặp.

Ví dụ 2

Input

2

Output

0

Giải thích

Với N=2 không thể có hai số cách nhau 2 cùng nằm trong phạm vi, nên kết quả là 0.

Thông tin học tập

• Module: M02
• Buổi: B07
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: functions, primality testing, twin primes, iterative counting
• Giới hạn kiến thức: B01-B07
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100