SPOJ Problem Set (classical)

3505. Prime Number Theorem

Problem code: CPRIME

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⁸) 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

Added by:	Ngô Minh Đức
Date:	2008-12-11
Time limit:	20s
Source limit:	50000B
Languages:	All except: ERL TECS JS
Resource:	© VNOI

hide comments


2009-12-17 10:38:11 kalycil for 5 , it is 2,3,5 , pi(x) =3 , 3 - 5/log(5) = .106*100/3=3.6
2009-07-17 08:39:06 Tony Beta Lambda As you see, pi(x) ~ x / logx, thus size of your array holding primes could be reduced.
2009-06-22 13:52:53 Daniel Ferizovic For the sieve I use an array of bool[10^8] and for the number of primes an array of int[10^8]. But I get a runtime error because of the memory, how to do it using less memory ? Last edit: 2009-06-22 14:10:00
2009-05-17 09:12:40 Zayakin_Andrey thanks, i understand
2009-05-16 23:03:11 Dominik Kempa pi(5)=3
2009-05-16 19:23:27 Zayakin_Andrey Please help, lets do example with x=5 pi(x)=1 abs(1-5/(ln5))/1*100=96.9 where is my mistake?