Check for Prime | Sample Video I for Essential Maths for CP | GeeksforGeeks
Вставка
- Опубліковано 29 вер 2024
- GeeksforGeeks presents you the Sample Video I for Essential Mathematics for CP.
Link for the course mentioned above - practice.geeks...
Our courses :
practice.geeks...
Please Like, Comment and Share the Video among your friends.
Install our Android App:
play.google.co...
If you wish, translate into the local language and help us reach millions of other geeks:
www.youtube.com...
Follow us on Facebook:
/ gfgvideos
And Twitter:
/ gfgvideos
Also, Subscribe if you haven't already! :)#competitiveprogramming #cp #checkforprime #cpcourse #gfg #geeksforgeeks
Simplicity level infinity
Sir what a fabulous explanation 🙏🙏
so what is the time&space complexity of the last method?
a third of the square root of n
Is all lecture of this course is taken by Sandeep sir ??
Yes DSA all course taken by sandeep sir
@@chandankumarram544
I am not telling about DSA course, this is a new course which are added in gfg 4/5 days ago..
@@billion_dreams__7787 This course has all lectures by Sandeep Jain
Great explanation with simplicity at it's peak for both problem and solver (Sandeep Sir).
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
why we increment by 6 i cannot under stand explain me some one
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
what about n=2 ,it gives the number itself as an output ,instead of 1(true);
What about 5? 5%5 is 0. It makes 5 is not a prime number
It will not enter inside the for loop for 5, so will return true at the end.
n should be greater than i , then only it will enter inside loop
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.
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?
@GeeksforGeeks
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).
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??
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.
@@h989l thank you so much
@@h989l Thanks man, it helped.
@@h989l omg sir! you are great teacher, solved my doubt! thanks a lottt!!!!
good explained......dear sir
What's the time complexity of the second more efficient method ?
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)
It is not work for 999983
my program works
Such good explanations 👌
GREAT !
very helpful for me sir, thank you
We can also look from 1 to √n to see if n is a prime number or not...
Running a loop from 1 would be a problem as any value of n would be divisible by 1.
Ya forgot about that...😀.. But is looping upto to √n more efficient or not??
Sir...what is the reason behind incrementing i to 6 every time in last approach....?
To improve performance for large n as number of iterations of for loop is reduced.
@@GeeksforGeeksVideos but why not 5 ,7 or any other number....why only choosed 6...?
@ram because we are checking with I and I+2 in one loop so next loop should start from I+6
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
@@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?