I think sometimes he tries and submits the ques beforehand 1 time before making the video. I have seen "Submitted 5 minutes : Accepted" from in the previous submission list a few times. xD Btw not saying it in a bad way, no one likes to do retakes for videos :| - I'm a big fan
There are indeed prime numbers greater than the number in its square. The smallest prime factor of a composite number n is less than or equal to root(n). So there is no point in checking further than the number as those get covered in the next numbers in the list and reduces complexity.
wouldnt be better checking all the numbers from 2 to half of the upper bound.. so 2 to n/2.. cause if u think about it, the factors must be less than or equal to half of the upper bound.. cause if it is bigger than n/2... (2 * factor ) > n
You didn't explain why this solution is faster than the O(n sqrt n) basic solution. Basically you have the sum n + n/2 + n/3 + n/5 +... + n/prime With prime
For anyone confused about i*i part, watch ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-T0XbxCYLBmc.html (no affiliation, I was one of the confused ones that googled around)
think of it as an if statement to check if the value of the current int squared is less than the value of n which is also the length of your primes array I think using n here makes more sense and involves less typing
Couldn't you also not do the count and just count how many you turned to true? In other words, if you have 20 elements in the array, you turn 15 of them from false to true, then you know the count would be 20 - 15, or 5. Saves that extra loop.
I think there is also no need for counting loop because when we go for negation in first loop that time we increment primeCount. may be Kevin I'm wrong :)
For those who are confused about i*i, let's consider-: 1. non prime number let's say 42 factors are 2*21(both are factors), 3*14, 6*7, 7*6, 14*3, 21*2 note these factors start repeating identically after square root i.e 6 (6*6) for numbers that are not prime and not multiple of primes, we would quickly find factor and break but for prime * prime type numbers we have to go till square root ex (11*13) (go till 12* 12) 2. prime number lets say 31 if this number was non prime based on factors done in step 1, we would have found something till square root of the number since, we didn't find we assume it to be prime, so ideally the analogy of factor is taken from non prime and applied to all numbers but it will optimised the prime and prime * prime type numbers because we stop at square root Complexity - O(sq1 + sq2 + ...sqN)
Coming from leetcode, knowing the solution already, this doesn't add much to it! ...I thought you could focus more on the non-obvious parts (e.g. i*i < n)
Hey Kevin, love your work. Great job. Its been a while I have been trying to learn dp and I always get stuck in the resources I should use and where should I start. It would be great if you could make some to help us
Any non-prime number will always have a factor that is less than or equal to its square root. For example, pick 36. It's factors are - 1*36, 2*18, 3*12, 4*9, 6*6. In each case, there is at least one number satisfying the above condition. So here, by considering all numbers up to the square root of n, we can successfully eliminate the non-prime numbers up to n. Hope this helps.
Hi Kevin, This was a great solution, but i was not able to understand line #9 (if(prime[i])), I understood that its optimizing the solution but not able to understand mathematically. Could you please explain with some example.
I think I'm dumb, but why wouldn't looping 0, n and checking if each number in between is a prime number work? I tried this but it would only pass some test cases. Can't figure out why.
think I just sieve of Eratosthenesed IN MY PANTS thanks for another great solution actually was able to get this one brute force styles but I was like mannn dis is ugly let's see what Kevin got up his sleeve was not disappointed lols
Hello, how you know that this problem was asked in google? can you tell more such problems which are not on leetcode. How to practice for google and other companies interviews.
The bruteforce method is actually super easy but leetcode won't accept my submission because of its n^2 runtime. Do you think most interviewers would accept the bruteforce method but then ask you to think about a potential better solution?
He DOES NOT solve them while recording it...I don't understand why people think he does lolol he learns about the problem, gets to a solution first, plans an explanation, and THEN records the video.
