Count Primes | LeetCode 204 | Theory + Python code (Sieve of Eratosthenes explained)
Vložit
- čas přidán 27. 07. 2024
- This video is a solution to LeetCode 204, Count Primes. I explain the question, go over the logic / theory behind solving the question and then solve it using Python. Sieve of Eratosthenes is explained to get the optimal solution to this question.
Comment below if you have a better solution to this problem!
Let me know if you have any feedback and don't forget to subscribe for more videos!
Time stamps:
0:00 Question explained
0:50 Brute force explained
3:03 Brute force python code
3:46 Sieve of Eratosthenes explained
13:44 Sieve of Eratosthenes python code
More leetcode questions solved:
• Add and Search Word - ...
instead of num*2 you can take num*num
Long time! Great video!!
I would love a better explanation of num * 2 argument for the last for loop
The basic idea is that when you get to a number where dp[num] = True that mean that the number itself IS a prime number. Since it is a prime number we would not want to set dp[current number] = False. Now by starting the loop from current number * 2 we skip the number itself and look at all its multiples
Say number = 7 (we know 7 is prime but all of 7's multiples must be true)
7 * 1 --> Is prime (do not change DP)
7 * 2 --> Not prime (change to dp[7*2] = False)
7 * 23--> Not prime (change to dp[7*3] = False)
...
and so on, but we just skip 7*1
@@saianishmalla2646 Thanks for making that clearer for me! I've appreciated your videos! They are helping me in my prep a lot!
Promo sm 🤦