Question

3) (i) How many primes are there below 2^{64}, approximately? To simplify calculations you may replace ln(2) by 0.5.

(ii) You want to find n such that the proportion of primes among the first n positive integers is at least 1/100. Then n must not exceed which number?

(iii) How many primes are there between 2^{128} and 2^{64}, approximately? To simplify calculations you may replace ln(2) by 0.5.

Answer 1

We know that if p(x) denotes number of primes less or equal to x then p(x)=x/logx approxiately.

i)p(2⁶⁴)=(2⁶⁴)/log(2⁶⁴)=(2⁶⁴)/(64log2)=2⁶⁴/32=2⁵⁹ approximately.

iii)p(2¹²⁸)=2¹²⁸/(log2¹²⁸)=2¹²⁸/(128log2) =2¹²⁸/64 =2¹²²

thus number of primes between 2⁶⁴ and 2¹²⁸

P(2¹²⁸)-p(2⁶⁴)=2¹²² -2⁵⁹ approximately...

ii)p(n)/n1/100

=>p(n)n/100.

=>n/lognn/100

=>logn100

=>ne^100