Skip to content

Instantly share code, notes, and snippets.

@vrat28

vrat28/check_prime.py

Created May 10, 2021 19:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vrat28/366dc254f3e9cc295d3bb0186e03a9dc to your computer and use it in GitHub Desktop.
Save vrat28/366dc254f3e9cc295d3bb0186e03a9dc to your computer and use it in GitHub Desktop.
Download ZIP
Sieve of Erathosthenes (Python)
Raw
check_prime.py
class Solution:
def countPrimes(self, n):
sieve = [0, 0] + [1] * (n - 1)
for k in range(ceil(n**0.5) + 1):
if sieve[k]:
for i in range(k*k, n+1, k):
sieve[i] = 0
return sum(sieve[:-1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment