Hai số nguyên dương \(A\) và \(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\) và \(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