One little issue I had when trying higher numbers. range(2, isqrt(n)) stops too early. For n = 1000, isqrt(n) = 31, which is prime. But since we don't include the stop value of range(), we don't mark 961 as False, giving an erroneous answer. The fix is easy, we stop at isqrt(n)+1 instead.
Be careful with mutable types, though. Here is an example. >>> xs = [[]] * 3 >>> xs [[], [], []] >>> xs[0].append(42) >>> xs [[42], [42], [42]] Basically, all elements of xs are the same list. To avoid this, you can write xs = [[] for _ in range(3)].
Great video, but I believe the range on "i" go to "isqrt(n) + 1" since the square of a prime is a composite number which has only two factors that are both equal to "isqrt(n)". If "n = p*p + 1" where p is a prime I believe the code you've shown here will incorrectly mark n-1 as prime (e.g. n=10 will return 9 as a prime).
You are absolutely correct. If n happens to be one more than a square of a prime my code gives the wrong answer! Please see my updated prime sieve video that does not suffer from this bug!
Great Video Dr Murphy I think NumPy can help speed it up as follows: import numpy as np n = int(1e6) # can be made into a function of course A = np.ones(n+1, dtype='int8') for i in range(2, int(n**0.5)+1): if A[i]: A[i**2::i] = 0 np.flatnonzero(A)[2:] # can be converted to a list Would appreciate your thoughts on this.
here is a simplified one for the loop causing errors without a need to import the library for i in range(2, int(n ** 0.5) + 1): the int method always returns the integer part of the fraction always.
@@mCoding Hello! Do you have any playlists over project Euler problems? I am beginner in python and some of these problems are difficult. If you have that'll be great!
@@mCoding yeah man I need your help! I am stuck on problem 11 of project Euler. I cannot share link because TH-cam's deleting it. Plus sir can you explainme how this block of code returns false for num=2( this code finds prime num. Ik 2 is a prime number lol but 2%2==0. Kinda confused here) def Prime_num(num): for i in range(2,int(num ** 0.5)+1): if num % i == 0: return False return True
Hi when I run the code the error: TypeError: 'type' object is not subscriptable occures. So python doesnt recognizes the list() function ??? Any help? Thx
I am new and copied the same code but it is not working is_prime = [True] * n this portion is not working, it is showing "Unindent does not match any outer indentation level" Please help me with the following.. :(
@@mCoding my friends and I are just getting into competitive programming So it would really nice to cover topic like ( Combinatorics problems, Prefix sum, Number of divisors, Graphs...) I will make sure that ur channel reach as much people as I know 😉
@@toomuchespresso13 This video was a long time ago but if I recall correctly the function returns the primes less than the input, not less than or equal to the input, so the base case should indeed be
One little issue I had when trying higher numbers. range(2, isqrt(n)) stops too early.
For n = 1000, isqrt(n) = 31, which is prime. But since we don't include the stop value of range(), we don't mark 961 as False, giving an erroneous answer.
The fix is easy, we stop at isqrt(n)+1 instead.
You have to stop at ceil( sqrt( n ) ).
@SirCorrino yeah! you are correct
OMG x = [True] * n makes a list of Truths with a len of 10, this is the most useful thing I have learned in my life
You can also do the same thing with strings, like "a" * 4 == "aaaa" :)
Be careful with mutable types, though. Here is an example.
>>> xs = [[]] * 3
>>> xs
[[], [], []]
>>> xs[0].append(42)
>>> xs
[[42], [42], [42]]
Basically, all elements of xs are the same list. To avoid this, you can write xs = [[] for _ in range(3)].
same, bro. Whenever I have to do that my ctrl and V buttons cower in fear. Advanced stuff.
@@abt8601 is this a bug or a feature. I cannot think of an example where this behavior could come handy.
Great video, but I believe the range on "i" go to "isqrt(n) + 1" since the square of a prime is a composite number which has only two factors that are both equal to "isqrt(n)". If "n = p*p + 1" where p is a prime I believe the code you've shown here will incorrectly mark n-1 as prime (e.g. n=10 will return 9 as a prime).
You are absolutely correct. If n happens to be one more than a square of a prime my code gives the wrong answer! Please see my updated prime sieve video that does not suffer from this bug!
Personally I skip root functions all together here and use a while:
while i**2
@@oida10000 o wise man!
Great Video Dr Murphy
I think NumPy can help speed it up as follows:
import numpy as np
n = int(1e6) # can be made into a function of course
A = np.ones(n+1, dtype='int8')
for i in range(2, int(n**0.5)+1):
if A[i]:
A[i**2::i] = 0
np.flatnonzero(A)[2:] # can be converted to a list
Would appreciate your thoughts on this.
I'm just wondering what is the time complexity of this code?
here is a simplified one for the loop causing errors without a need to import the library
for i in range(2, int(n ** 0.5) + 1):
the int method always returns the integer part of the fraction always.
isqrt is faster and is from a built-in library. also he knows that lol
thanks. i am a huge fan of yours from india. your coding lessons are very good
Your 2 minute explanation was enough, thank you
Really Great content! Hope you keep making these kind of videos!
Thanks for the support!
@@mCoding Hello! Do you have any playlists over project Euler problems? I am beginner in python and some of these problems are difficult. If you have that'll be great!
Not yet, only so much time in the day. If you have a specific problem you'd like to see, I take requests!
@@mCoding yeah man I need your help! I am stuck on problem 11 of project Euler. I cannot share link because TH-cam's deleting it.
Plus sir can you explainme how this block of code returns false for num=2( this code finds prime num. Ik 2 is a prime number lol but 2%2==0. Kinda confused here)
def Prime_num(num):
for i in range(2,int(num ** 0.5)+1):
if num % i == 0:
return False
return True
Also thanks for helping
Man your video is awesome hope to see more from you like this
Thanks! More on the way...
@@mCoding Can you do videos on complexity of various python functions and which one is best for some common Problems?
@@achuthkarthik4689 Do you have any problems in mind that you'd like to see?
@@mCoding I got a simple problem to find maximum sum of increasing range in an array though i solved it i need a more efficient algorithm.
If you can post a link to the problem description, I'll take a look.
How long it takes to find all primes in range (0 - 1 000 000 000)?
Order of O(n.log(log(n)))
@@sasidharnaidu4507 And exactly...? Because I have 3s on Ryżem 5500.
I suppose it doesn't really matter much but the function having two lists bugs me hahaha
I see you made another video about this, I'll check it out
I cant find this code in your github. Whats the name of it?
Great Explanation!
Cheers!
Glad it was helpful!
What is the time complexity of the algorithm in here ?
O(n log log n) i believe
Hi when I run the code the error: TypeError: 'type' object is not subscriptable occures. So python doesnt recognizes the list() function ???
Any help? Thx
when i run it on Replit website it gaves me the same error as you but on my local computer it worked well.
I am new and copied the same code but it is not working is_prime = [True] * n this portion is not working, it is showing "Unindent does not match any outer indentation level" Please help me with the following.. :(
This means somewhere in you file your indentation is not correct, probably a stray tab or space somewhere.
Great video!
Keep it up 😉
Thank you! Let me know if there are any topics you would like me to cover!
@@mCoding my friends and I are just getting into competitive programming
So it would really nice to cover topic like ( Combinatorics problems, Prefix sum, Number of divisors, Graphs...) I will make sure that ur channel reach as much people as I know 😉
but 2 isn't prime as u said...
Is_prime[2]=False?
2 is a prime number :)
@@mCoding you should have the base case
@@toomuchespresso13 This video was a long time ago but if I recall correctly the function returns the primes less than the input, not less than or equal to the input, so the base case should indeed be
Well, i got the wrong output
from math import isqrt
def iss(n):
if n
if the num == 5 it returns 4 yet not a prime
USE
for i in range(2,isqrt(n)+1):
Trying to remember Sieve_of_Eratosthenes as a reference name would cause explosion
Sir, I have a problem which I want to solve with the help of python but I am not an expert in python please help me?
Thank you
improve explaining the code line by line