Can anyone explain the given blog of few lines.
[link text][1]
Also few doubts related blog:-
In seive eratotheneses algorithm why the loop goes upto sqaure root of given number only? why not till n.
In prime factorization of n why loop goes upto sqaure root of n and not till n.
How time complexity of seive is O(nloglogn). And for prime factorization of a number -O(squareroot of n)
[1]: http://codeforces.com/blog/entry/7262
answer for 2)
let number n be the product m primes
n=p1p2p3*…pm.
where p1,p2… and pm are primes.
Now we can say that atmost only one prime among (p1,p2,…pm) is greater than square root of n.
this is can be proved in this way
let’s say pi,pj are two primes among (p1,p2,…pm) and both are greater than square root n
then pi*pj>(sqrt(n)*sqrt(n))
pi*pj>n which is false.
this is the reason why we iterate only upto sqrt(n) is prime factorisation and finally if n is not equal to 1 then that n is also a prime factor.
I didn’t read the blog yet, but here is the related answer of your queries:
Ans: According to prime number def. They are those number which can be divisible by both 1 and themselves only. So the possibility that a number can be divisible is only up to sqrt(n).
Basically, we are gonna check up to N/2 to prove our statement.
Let’s proof this by example:
N = 9
sqrt(9) = 3
9 can be divisible by a number greater than 3 but covered in selected range(2,3)
N = 25
sqrt(25) = 5
25 can be divisible by a number greater than 5, but they are already covered in range(2,3,5)
EDIT:
N = 36
sqrt(36) = 6
It include numbers 2,3,5
2 - (4,6,8,10,12,14,16,18…) covered all this number
3 - (6,9,12,15,…)
5 - (10,15,20,…)
Let’s take 7 which is greater than 6
7-(14,21,…)
but these numbers are already covered, that’s why we take sqrt(n) instead of going to N or N/2.
What if we take 36? 36 is divisible by a number >6 , i.e. 12 and 18. Also, what if we take 6. sqrt(6) = 2 (int). But there is a prime number greater than 2 which divides 6 (i.e. 3).
OR, take 14. 14 is also divisible by a number greater than sqrt(14), that too prime. Can you please clarify yourself here? 
I think hruday968 is right when he said that - Now we can say that atmost only one prime among (p1,p2,....pm) is greater than square root of n.
For time complexity of sieve, you should give quora a search. A derivation is given on that site. The log(logn) term came from summation of series or something similar.
oh, didn’t think that way.I will edit my answer in a while.Thanks for correcting me @vijju123
Feel free to edit, If I am wrong
Thanks anyways.
There is a chance of atmost one prime from(p1,p2…pm)to be greater than sqaure root of n. BUT loop DOES NOT goes beyond square root of n.SO how these prime will be counted in prime factorization.
For ques 2 Shouldn’t it be like this :
There is atleast one prime factor of a given number less than sqrt(n) So If the number is composite it will meet its smallest prime factor in only sqrt(n) iterations.
Though I don’t have a mathematical proof but it’s true for every case that there is atleast one prime factor less than sqrt(num)
@vijju123 you can also check it for 14 and 6 or any of the number .
Moreover talking about sieve you can check it easily .If I have iterated over sqrt(N) that means that for all numbers till n i have the smallest prime factor(at least) so all numbers will be storing their smallest prime factor(say in a vector). So if you want its prime factorization (of any number ) just go to the number you know its smallest prime factor go on dividing by the prime factors you will get whole prime factorization in O(logN).
Hope this Helps Please correct if i am wrong.
in for loop you will divide n with the prime number if that prime is a factor of n.after the for loop you should check whether n becomes 1 or not,if n is not equal to 1 then that remaining n will be prime factor greater square root of initial n.
Example:
let n be 14,for loop goes upto 3.As 2 divides n then we divide n by 2 and n becomes 7.Now for loop ends n will be 7 which is our required prime number greater than square root of 14.