Sir the more efficient method can be little more efficient if you calculate the square root before the for loop because in for loop it runs again and again for same number Like int root = (int)Math.sqrt(n); for (int i = 5; i
i think it will be theta(√n/6) but i am confused for big O as in that we dont consider the constants which is 1/6 in this case so Big O might be O(√n) but i am sure of theta(√n/6)
in last most efficient method we put in i=i+6 but only check for n%i==0 and n%(i+2)==0 . for other numbers which are even like i+1,i+3,i+5, it doesnt need to check, but for i+4 we dont check n%(i+4)==0. What is the reason behind the same?
see in loop we are iterating for i=3k+2 for some k. eg. 5,11,17,23,29........ This shows that i+4 will be 3k+6 anyway will be multiple of 3. i+2 will be 3k+4 or 3t+1 type. Hence, we need not check for i+4
@@jaijaijaijai123 So lets take 5=3(1)+2 let initial value of k =1 Then, [ 3k+2, 3k+2+6 ) =[ 3k+2, 3k+2+3(2) ) =[ 3k+2, 3(k+2)+2) 5= 3(1) +2 11= 3(3) +2 17 = 3(5) +2 . . . and so on so we need to check for interval [3k+2, 3(k+2)+1) everytime. -- 3k+2 and 3k+4 are check inside iteration. -- 3k+3 is divisible by 3 -- 3k+5 not checked -- 3k+6 is divisible by 3 -- 3k+7 not checked -- 3k+8 = 3k+ 6 +2 = 3(k+2)+2 so it ends here The question still remains that 3k+5 and 3k+7 arent checked in each iteration. There is only one reason that remains, that somehow 3k+5 and 3k+7 are proved to be even numbers ( i noticed k is always odd, this might give some hint).
So guys read my comment so that you won't waste 2days to understand this. basic logic is if x divides n the n/x also divides n So lets take (x,n/x )as a pairs as x increase n/x decreases suppose they became equal at some point then x would be sqrt(n) If any factor which is >sqrt(n) repeat the pair of factors support (3,9) for 27 math.sqrt(27) =5 so lets take 9 so the pair now become (9,3) so iterating upto √n saves runtime
because if you look at the loop, it is starting from 5 right, it means it is incrementing like this 5,5+6=11,11+6=17,... let's see the numbers between 5 and 11, the numbers are 6,7,8,9,10; inside a loop we are checking for i and i+2, so when i=5 , we check for 5 and 7 right .so 7 is already checked so we are actually eliminating 6,8,9,10 right . now look at those numbers they are in the form of 2n or 3n(where n is natural numbers) .the fun part is we already checked for 2 and 3 in the starting of the loop like this if (n%2 == 0 || n%3 == 0) return false. so we actually checked for all numbers but in a efficient way.
Bro we are not doing any other except I+6 because it covers all prime number like 11,13,17,19 and these are the only numbers which divide its square like 121,169 etc so we do I+6
