E. TWINS - Nguyên tố sinh đôi

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Trong lý thuyết số, hai số nguyên tố p q được gọi là cặp số nguyên tố sinh đôi nếu q–p=2 . Ví dụ: các cặp số (3,5),(5,7),(11,13),(17,19) là các cặp sinh đôi. Trong trường hợp tổng quát, với số nguyên dương k cho trước, cặp số nguyên tố p q được gọi là sinh đôi nếu q–p=k . Ví dụ: với k=4 cặp số nguyên tố (3,7) được gọi là sinh đôi.

Yêu cầu: Cho n k\ (1≤k≤n≤10^6) . Hãy xác định số cặp sinh đôi trong phạm vi từ 1 đến n (thỏa mãn q–p=k ).

Dữ liệu vào:

  • Một dòng duy nhất chứa hai số nguyên n k .

Dữ liệu ra:

  • Một số nguyên là số lượng cặp sinh đôi tìm được.

Ví dụ:

Dữ liệu vào:

17 2

Dữ liệu ra:

3

Giải thích: Ta có các cặp thỏa mãn là (3,5),(5,7),(11,13) .

Giới hạn:

  • Subtask \#1: 80\% số điểm có n≤10^4 ;
  • Subtask \#2: 20\% số điểm còn lại có 10^4< n≤10^6 .