CPRIME - Prime Number Theorem


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 ≤ 108) 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
shishir_09: 2017-12-12 22:32:41

A sieve of 1e8 + Precalc made the problem AC just right now :D

sas1905: 2017-06-26 02:08:11

Bitwise sieve + Binary search.

rohit9934: 2017-06-19 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.
Bitwise sieve is designed for tackling masochistic memory constraints.

sandeep_4141: 2017-05-30 16:59:50

Only Bitwise sieve can save you :)

Shubham Jadhav: 2017-05-14 20:05:32

sieve with 1e8 works in C++ :)

raghav_7050: 2017-01-31 02:41:20

bitwise seive + vector and a lil pre-comp. ----> piece of cake !!

spartax: 2016-12-11 07:15:27

very nice problem. Use bitset and upper_bound

himanshu_0896: 2016-11-29 14:56:47

How to deal with 10^7 <= x <= 10^8 ?

dwij28: 2016-10-15 23:59:41

Easy one for C++. Use upper_bound and bitsets.

Anuj Arora: 2016-09-05 08:16:46

Just a minor optimization in sieve ....AC!!!


Added by:Duc
Date:2008-12-11
Time limit:1.812s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI