Check for Prime | Sample Video I for Essential Maths for CP | GeeksforGeeks

[@Raj_Tanvar]

Great explanation with simplicity at it's peak for both problem and solver (Sandeep Sir).

[@zrotrasukha8733]

I watched like more than 2 hours of lecture on this and still didn't understand, watched this 20 minute video and it is so crystal clear.

[@superfact4556]

Simplicity level infinity

[@GrowwithVivek08]

Sir what a fabulous explanation 🙏🙏

[@sumittanwar7727]

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

[@bazar9000]

Such good explanations 👌

[@mahedirony]

good explained......dear sir

[@MahamudulHasanSiam]

very helpful for me sir, thank you

[@surjeetsingh-cp6hn]

what about n=2 ,it gives the number itself as an output ,instead of 1(true);

[@vivek_1012]

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?

[@vivek_1012]

@GeeksforGeeks

[@jaijaijaijai123]

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

[@vivek_1012]

​@@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).

[@chiragagrawal3501]

What's the time complexity of the second more efficient method ?

[@ACEAMI]

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)

[@aryanyadav3926]

GREAT !

[@utkarshmaurya6877]

We can also look from 1 to √n to see if n is a prime number or not...

[@GeeksforGeeksVideos]

Running a loop from 1 would be a problem as any value of n would be divisible by 1.

[@utkarshmaurya6877]

Ya forgot about that...😀.. But is looping upto to √n more efficient or not??

[@CengizAkarsu]

so what is the time&space complexity of the last method?

[@danielmaralending6732]

a third of the square root of n

[@aishwaryakg2411]

in the more efficient method why are we incrementing it by 6 and y are we checking for both n%i and n%i+2 ???? can some one please do answer??

[@h989l]

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.

[@aishwaryakg2411]

@@h989l thank you so much

[@madhabkafle8072]

@@h989l Thanks man, it helped.

[@nafisaparveen9759]

​@@h989l omg sir! you are great teacher, solved my doubt! thanks a lottt!!!!

[@pavitragupta26]

@@h989l You say 7 is already checked. So, we are actually eliminating 6,8,9,10. Now look at those numbers they are in the form of 2n or 3n( where n is natural number). How by checking for 7 we are already eliminating 6,8,9,10? please elaborate. Please elaborate why we are doing i+6 is the loop? Thanks!

[@factsmotivation7728]

why we increment by 6 i cannot under stand explain me some one

[@billion_dreams__7787]

Is all lecture of this course is taken by Sandeep sir ??

[@chandankumarram544]

Yes DSA all course taken by sandeep sir

[@billion_dreams__7787]

@@chandankumarram544 I am not telling about DSA course, this is a new course which are added in gfg 4/5 days ago..

[@GeeksforGeeksVideos]

@@billion_dreams__7787 This course has all lectures by Sandeep Jain

[@3lpme]

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

[@ramsai6141]

Sir...what is the reason behind incrementing i to 6 every time in last approach....?

[@GeeksforGeeksVideos]

To improve performance for large n as number of iterations of for loop is reduced.

[@ramsai6141]

@@GeeksforGeeksVideos but why not 5 ,7 or any other number....why only choosed 6...?

[@bhanupratapsingh5468]

@ram because we are checking with I and I+2 in one loop so next loop should start from I+6

[@yourbestie4138]

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

[@omkargunjal1611]

@@yourbestie4138 well apart from detecting prime, can we say that a = 5 and d=6 and any n can give us a prime number always?

[@robertb4082]

What about 5? 5%5 is 0. It makes 5 is not a prime number

[@GeeksforGeeksVideos]

It will not enter inside the for loop for 5, so will return true at the end.

[@bhanupratapsingh5468]

n should be greater than i , then only it will enter inside loop

[@cosmicray.sagor1]

It is not work for 999983

[@jaijaijaijai123]

my program works