We Will Be Counting Primes

The function π ( x ) \pi(x) gives the number of primes less or equal to x x . Find the first three digits of π ( 2 × 1 0 11 ) \pi( 2 \times 10^{11} ) .


The answer is 800.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Vighnesh Raut
Oct 24, 2014

We can solve it mathematically too. We know that Π ( x ) = 2 x d t l o g ( t ) \Pi (x)=\int _{ 2 }^{ x }{ \frac { dt }{ log(t) } } . So, just putting the value of 'x' as 2 x 1 0 11 10^{11} we get answer as 8.007 x 1 0 9 10^{9}

Did the same way :)

Swapnil Das - 5 years, 4 months ago

I used Sage for this one:

prime_pi(2*10^11)

But for a true algorithm, see this

The simplest is Sieve of Eratosthenes

Explain me the music symbols in the Question title, please?

I believe it's a song. @Thaddeus Abiy could you clarify that?

Tan Li Xuan - 7 years ago

Counting Stars ,One Republic.It is really popular,unless you don't listen to music or have been living in a cave. :p

Thaddeus Abiy - 7 years ago

Log in to reply

Oh and PS I don't think a sieve would work here. Considering the size of the input,you would need a very powerful computer. The answer can be easily obtained by looking at the first three digits of the following definite integral( Logarithmic integral function )l π ( x ) L i ( 2 × 1 0 11 ) = 0 2 × 1 0 11 d x l n ( x ) \pi(x) \approx Li(2\times 10^{11}) =\int _{ 0 }^{ 2\quad\times10^{11} }{ \frac { dx }{ ln(x) } } . This method doesn't always work though.

Thaddeus Abiy - 7 years ago

Log in to reply

It cant be solved efficiently given the constraints so the best bet will be to use the logarithmic integral function .

sidhant bansal - 6 years, 11 months ago

Yup. I used that method and got 768 not 800... :H

Satvik Golechha - 6 years, 11 months ago

I don't listen to music :)

Tan Li Xuan - 6 years, 11 months ago

Hey Thaddeus, I am totally new to CS. I just know HTML... Would u pls suggest me a source where I could start from scratch and go upto advance level...

Pankaj Joshi - 6 years, 11 months ago

Log in to reply

netuts is supposed to be really good

Thaddeus Abiy - 6 years, 11 months ago
Kenny Lau
Aug 29, 2014

Java code:

public class brilliant{
    public static void main(String args[]){
        int res = 0;
        long[] primes = new long[0];
        for(long i=2;i<200000000000L;i++){
            boolean isPrime = true;
            for(int j=0;j<primes.length;j++) if(i%primes[j]==0) isPrime = false;
            if(isPrime){
                primes = add(primes,i);
                res++;
            }
        }
        System.out.println(res);
    }
    private static long[] add(long[]a, long b){
        long[] res = new long[a.length+1];
        for(int i=0;i<a.length;i++) res[i]=a[i];
        res[a.length]=b;
        return res;
    }
}

(Just kidding, I used WolframAlpha for this one)

We already have Sage.

It's rich cousin*, Mathematica:

FromDigits[IntegerDigits[PrimePi[2*10^11]][[;; 3]]]

returns

800

* all respect to Sage, it is wonderful free as it is.

Drop TheProblem
Aug 24, 2014

using Eulero's φ(2x10^11)=φ(2x2^11x5^11)=φ(2^12x5^11) we get φ=2^12x5^11x(1-1/2)x(1-1/5)=8x10^10. So answer is 800

Note that this function counts the number of integers that are coprime to x x , as opposed to the number of integers that are prime.

You will include all the odd composite numbers in your count.

The correct value is approximately 8.007 × 1 0 9 8.007 \times 10^9 .

Calvin Lin Staff - 6 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...