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

View as PDF

Submit solution

Points: 300.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Hai số nguyên dương AB đượ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, AB có cùng độ dài và khác nhau chính xác một chữ số. (Ví dụ {158,198} 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( hoặc B) thì ta sẽ thu được B( hoặc A) (Ví dụ {47,147} 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ố a0,a1,....aq thỏa mãn điều kiện sau:

  • a0=2;aq=G

  • {ai,ai+1} là cặp số "hàng xóm" và aiP,ai+1P với mọi 0iq1(qN)

  • aiG 0iq

(Trong đó 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(1N10000000)

Output:

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

Ví dụ :

Input:

11

Output:

11

Giải thích: 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

Subtask:

  • 20% test có 1N1000

  • 80% test có 1000N10000000


Comments

Please read the guidelines before commenting.


There are no comments at the moment.