ACM ICPC 2014-This year problems were hard as many good teams could solve only 3-4 problems. This time IIT Indore (A new IIT) secured the first place among Indian Colleges beating big colleges like IIIT Hyd,IIT Bombay,IIT Madras,IIT Roorkee . Congratulations to all the teams after all going for ICPC World Finals is in itself a big achievement .
This week I was a little busy in answering the queries of some curious souls who just now cleared JEE and about to join the premier institutes of the country, it always feels good to guide someone who is asking for your opinion.I always advise people to opt for that stream/branch in which they have interest .
I took a break from my Topcoder practice and started SPOJ problems . For the first time I successfully applied a top down Dynamic Programming approach in 1 question . I was waiting for this moment for past 2/3 months . It feels very good after seeing a problem solved after so many unsuccessful attempts .
Sieve of Eratosthenes -
I learnt how to apply Sieve of Eratosthenes. This method is very fast(for numbers of the order of some millions) to find whether a given no. is prime or not . The approach is simple, suppose we have a no. N we want to find whether this no. is prime or not we just need to look at all the primes <=Square root(N) lets say we want to know whether 431 is prime or not so we need
Sqrt(431) ~20.7 we just need to check whether primes <20 i.e. 2,3,5,7,11,13,17,19 can divide this no. or not .
So, 431 is an odd no. so not div by 2
sum of digits is 8 so not div by 3
end digit is 1 so not div by 5
431%7!=0 , 431%11!=0,431%13!=0,431%17!=0 and 431%19!=0 . Ohh! I took a random no. and it was a prime! I need to find the probability of finding a prime no. randomly from the set of natural no. :P Just kidding :D . Recently, I found out that this probability is inversely proportional to the logarithm of the chosen number N .
So this is how Sieve works and if you know all the prime less than sqrt(N) then this method is very fast .
Thanks for reading and keep coding .
This week I was a little busy in answering the queries of some curious souls who just now cleared JEE and about to join the premier institutes of the country, it always feels good to guide someone who is asking for your opinion.I always advise people to opt for that stream/branch in which they have interest .
I took a break from my Topcoder practice and started SPOJ problems . For the first time I successfully applied a top down Dynamic Programming approach in 1 question . I was waiting for this moment for past 2/3 months . It feels very good after seeing a problem solved after so many unsuccessful attempts .
Sieve of Eratosthenes -
I learnt how to apply Sieve of Eratosthenes. This method is very fast(for numbers of the order of some millions) to find whether a given no. is prime or not . The approach is simple, suppose we have a no. N we want to find whether this no. is prime or not we just need to look at all the primes <=Square root(N) lets say we want to know whether 431 is prime or not so we need
Sqrt(431) ~20.7 we just need to check whether primes <20 i.e. 2,3,5,7,11,13,17,19 can divide this no. or not .
So, 431 is an odd no. so not div by 2
sum of digits is 8 so not div by 3
end digit is 1 so not div by 5
431%7!=0 , 431%11!=0,431%13!=0,431%17!=0 and 431%19!=0 . Ohh! I took a random no. and it was a prime! I need to find the probability of finding a prime no. randomly from the set of natural no. :P Just kidding :D . Recently, I found out that this probability is inversely proportional to the logarithm of the chosen number N .
So this is how Sieve works and if you know all the prime less than sqrt(N) then this method is very fast .
Thanks for reading and keep coding .
No comments:
Post a Comment