The function π ( x ) gives the number of primes less or equal to x . Find the first three digits of π ( 2 × 1 0 1 1 ) .
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.
Did the same way :)
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?
Counting Stars ,One Republic.It is really popular,unless you don't listen to music or have been living in a cave. :p
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 1 1 ) = ∫ 0 2 × 1 0 1 1 l n ( x ) d x . This method doesn't always work though.
Log in to reply
It cant be solved efficiently given the constraints so the best bet will be to use the logarithmic integral function .
Yup. I used that method and got 768 not 800... :H
I don't listen to music :)
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...
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.
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
Problem Loading...
Note Loading...
Set Loading...
We can solve it mathematically too. We know that Π ( x ) = ∫ 2 x l o g ( t ) d t . So, just putting the value of 'x' as 2 x 1 0 1 1 we get answer as 8.007 x 1 0 9