CPRIME  Prime Number Theorem
English  Vietnamese 
In number theory, the Prime Number Theorem describes the asymptotic distribution of prime numbers. Let π(x) be the number of prime numbers not greater than x. The Prime Number Theorem states that:
Your task is to write a program to verify how well the Prime Number Theorem can estimate π(x). To be more precise, for a given x, you have to calculate the percent error π(x)  x/lnx / π(x) %.
Input
The input contains several test cases (no more than 1000). Each test case contains a value of x (2 ≤ x ≤ 10^{8}) given in one line. A number 0 terminates the input.
Output
For each value of x, output the percent error of the estimation of π(x), rounded to 1 decimal digit.
Example
Input: 10000000 2 3 5 1234567 0 Output: 6.6 188.5 36.5 3.6 7.7
hide comments
scolar_fuad:
20190509 16:12:45
Ac in first go use bitwisw seive to avoid TLE and keep cumulative sum of prime numbers 

crackeree:
20181229 23:14:40
first attempt :)


shishir_09:
20171212 22:32:41
A sieve of 1e8 + Precalc made the problem AC just right now :D 

sas1905:
20170626 02:08:11
Bitwise sieve + Binary search. 

rohit9934:
20170619 20:32:41
Don't know the point of using bitwise sieve over traditional sieve when bitwise is using 390M (0.36 s)in the judge.


sandeep_4141:
20170530 16:59:50
Only Bitwise sieve can save you :) 

Shubham Jadhav:
20170514 20:05:32
sieve with 1e8 works in C++ :) 

raghav_7050:
20170131 02:41:20
bitwise seive + vector and a lil precomp. > piece of cake !! 

spartax:
20161211 07:15:27
very nice problem. Use bitset and upper_bound 

himanshu_0896:
20161129 14:56:47
How to deal with 10^7 <= x <= 10^8 ? 
Added by:  Duc 
Date:  20081211 
Time limit:  1.812s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  © VNOI 