def primes_upto(limit: int):
"""Generate prime numbers < *limit*."""
# Sieve of Eratosthene
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n # found prime number
for c in range(n*n, limit, n): # start with square, less values are marked already
is_prime[c] = False # mark composites
if __name__ == "__main__":
from itertools import islice
print(*islice(primes_upto(100), 10)) # -> 2 3 5 7 11 13 17 19 23 29
Yeah, but yours was generated by the "post unoptimized code to HN and wait for someone to optimize it" model, which, although free and doesn't require a GPU, is a much slower model.
Someone should turn this into a product! You highlight the code you want to optimize, and it posts it to hn as a semi-contextually-appropriate comment to invite code golfing, and the highest rated reply gets posted back to your repo as a PR.
But, unless you are trying to find a prime number low enough that you might as well look it up in a pre-generated table, it might still be end-to-end more efficient?
