Finding Primes in Python with the Sieve of Eratosthenes

Implement this algorithm for finding primes in Python.

SUPPORT ME ⭐
---------------------------------------------------

BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------

MUSIC
---------------------------------------------------
Track: Stardust — JayJen [Audio Library Release]
Music provided by Audio Library Plus

[SirCorrino]

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.

[xfrijolito]

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

[slamprogram]

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).

[michaeltwiton]

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.

[aynuayex]

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.

[alperkaya]

Your 2 minute explanation was enough, thank you

[_subhambanerjee]

thanks. i am a huge fan of yours from india. your coding lessons are very good

[atharvaathalye]

Really Great content! Hope you keep making these kind of videos!

[achuthkarthik]

Man your video is awesome hope to see more from you like this

[re.liable]

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

[haisomeone]

What is the time complexity of the algorithm in here ?

[Xaminn]

Trying to remember Sieve_of_Eratosthenes as a reference name would cause explosion

[marcindj]

How long it takes to find all primes in range (0 - 1 000 000 000)?

[mikeborg]

I cant find this code in your github. Whats the name of it?

[jakobj]

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

[atharva]

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.. :(

[indrajithlal]

but 2 isn't prime as u said...
Is_prime[2]=False?

[_newideas]

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?

[bikeshregmi]

Well, i got the wrong output

from math import isqrt
def iss(n):
if n<=2:
return []
isprime=[True]*n
isprime[0]=False
isprime[1]=False
for i in range(2, isqrt(n)):
if isprime[i]:
for x in range(i*i, n, i):
isprime[x]=False
return [i for i in range(n) if isprime[i]]
iss(10)

[2, 3, 5, 7, 9]

[KillaniSurya]

improve explaining the code line by line