Cặp số "hàng xóm"

Xem PDF



Tác giả:
Dạng bài
Điểm: 600 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hai số nguyên dương \(A\)\(B\) được gọi là cặp số "hàng xóm" nếu chúng thỏa mãn \(1\) trong \(2\) điều kiện sau:

  • Trong biểu diễn thập phân, \(A\)\(B\) có cùng độ dài và khác nhau chính xác một chữ số. (Ví dụ \(\left\{158,198\right\}\) là cặp số "hàng xóm")

  • Nếu ta thêm một chữ số vào bên trái của \(A(\text{ hoặc }B)\) thì ta sẽ thu được \(B(\text{ hoặc }A)\) (Ví dụ \(\left\{47,147\right\}\) là cặp số "hàng xóm")

Bây giờ, ta gọi số nguyên tố \(G\) là "bà con" với số \(2\) nếu tồn tại một chuỗi số \(a_0,a_1,....a_q\) thỏa mãn điều kiện sau:

  • \(a_0=2;a_q=G\)

  • \(\left\{a_i,a_{i+1}\right\}\) là cặp số "hàng xóm" và \(a_i\in \mathbb{P},a_{i+1}\in \mathbb{P}\) với mọi \(0\le i\le q-1(q\in \mathbb{N}^{*})\)

  • \(a_i\le G\text{ }\forall 0\le i\le q\)

(Trong đó \(\mathbb{P}\) là tập hợp các số nguyên tố.)

Nói cách khác, tồn tại một dãy chuyển hóa \(2\) thành \(G\) mà tất cả các số trong dãy là số nguyên tố, hai số kề nhau phải là "hàng xóm" và tất cả các số trong dãy không quá \(G\).

Ví dụ, \(31\) là số "bà con" với \(2\) vì ta có dãy sau: \(2, 7, 17, 11, 31\).

Cho số nguyên dương \(N\) và gọi \(F(N)\) là tổng của tất cả các số nguyên tố không quá \(N\) và không "bà con" với số \(2\).

Yêu cầu:

  • Nhập số nguyên dương \(N\). In ra \(F(N)\) tương ứng.

Input:

  • Một dòng duy nhất chứa số nguyên dương \(N(1\le N\le 10000000)\)

Output:

  • In ra đáp án cần tìm.

Scoring:

  • Subtask \(1\) (\(20\%\) số điểm): \(1\le N\le 1000\)
  • Subtask \(2\) (\(80\$\) số điểm): \(1000\) \(\le N \le\) \(10000000\)

Example

Test 1

Input
11
Output
11
Note

Từ \(1\) đến \(11\) chỉ có duy nhất số \(11\) là số nguyên tố không "bà con" với số \(2\) nên đáp án là \(11\)


Bình luận

Không có bình luận nào.