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

GeeksforGeeks presents you the Sample Video I for Essential Mathematics for CP.

Our courses :

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into the local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)#competitiveprogramming #cp #checkforprime #cpcourse #gfg #geeksforgeeks

[zrotrasukha]

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.

[Raj_Tanvar]

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

[sumittanwar]

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 <= root; i +=5)
later continuing your solution .

[lpme]

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

[surjeetsingh-cphn]

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

[utkarshmaurya]

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

[chiragagrawal]

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

[vivek_]

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?

[CengizAkarsu]

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

[factsmotivation]

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

[aishwaryakg]

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??

[billion_dreams__]

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

[ramsai]

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

[robertb]

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