Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT123I - Định lý Chebyshev

Nếu n là một số nguyên dương, thì tồn tại ít nhất một số nguyên tố lớn n và nhỏ hơn hoặc bằng 2n. Đó gọi là định lý Chebyshev hoặc định lý Bertrand-Chebyshev. Ví dụ: Có 4 số nguyên tố mà lớn hơn 10 và không lớn hơn 20, là 11,13,17 và 19.  Có 3 số nguyên tố lớn hơn 14 và không lớn hơn 28, là 17,19 và 23.

Viết chương trình đếm số các số nguyên tố và lớn hơn n và nhỏ hơn hoặc bằng 2n.

Input

Gồm nhiều bộ test, mỗi bộ test trên một dòng chứa số nguyên dương duy nhất n (n<=123456).

Dữ liệu kết thúc bởi dòng chứa số 0.

Output

Với mỗi bộ test, in ra trên 1 dòng chứa số các số nguyên tố lớn hơn n và nhỏ hơn hoặc bằng 2n.

Example

Input:

1

10

13

100

1000

10000

100000

0

Output:

1

4

3

21

135

1033

8392


Được gửi lên bởi:Admin
Ngày:2012-03-03
Thời gian chạy:0.166s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-09-29 09:09:38 Cường D14AT1
B1.sàng nguyên tố
B2.Gọi mảng d[i] là số lượng snt từ 1..i (có tính i)
=> từ n..2n có d[2n]-d[n] snt
2014-06-23 14:39:58 ...
mảng động.

Last edit: 2014-09-27 20:32:07
2014-03-06 14:06:30 UZU_CODER_ Ð
hay chăng là sàng nguyên tố
2013-04-14 11:22:27 Phạm Trung Kiên C13CN3
chặt nhị phân còn TLE
chả có nhẽ mảng hằng @@
2013-03-04 17:01:08 Trần Vãn Dương D10CN2
Do phuc tap 1 ty
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.