Finding Primes in Python with the Sieve of Eratosthenes
ฝัง
- เผยแพร่เมื่อ 27 มิ.ย. 2024
- Implement this algorithm for finding primes in Python.
― mCoding with James Murphy (mcoding.io)
Source code: github.com/mCodingLLC/VideosS...
SUPPORT ME ⭐
---------------------------------------------------
Patreon: / mcoding
Paypal: www.paypal.com/donate/?hosted...
Other donations: mcoding.io/donate
BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------
Discord: / discord
Github: github.com/mCodingLLC/
Reddit: / mcoding
Facebook: / james.mcoding
MUSIC
---------------------------------------------------
Track: Stardust - JayJen [Audio Library Release]
Music provided by Audio Library Plus
Watch: • Stardust - JayJen | Fr...
Free Download / Stream: alplus.io/stardust - วิทยาศาสตร์และเทคโนโลยี
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 ) ).
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!
Your 2 minute explanation was enough, thank you
Great Explanation!
Cheers!
Glad it was helpful!
thanks. i am a huge fan of yours from india. your coding lessons are very good
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.
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.
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?
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 😉
Thank you
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?
What is the time complexity of the algorithm in here ?
How long it takes to find all primes in range (0 - 1 000 000 000)?
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.
Trying to remember Sieve_of_Eratosthenes as a reference name would cause explosion
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.
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):
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?
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
improve explaining the code line by line