Skip to content

Instantly share code, notes, and snippets.

@theXYZT
Last active March 1, 2021 02:01
Show Gist options
  • Save theXYZT/5b5debfcdf8d91a35ad42b0f5a403b9b to your computer and use it in GitHub Desktop.
Save theXYZT/5b5debfcdf8d91a35ad42b0f5a403b9b to your computer and use it in GitHub Desktop.
Generate smooth numbers
import itertools
def times(n, g):
for i in g:
yield n * i
def merge(g, h):
ng = next(g)
nh = next(h)
while 1:
if ng < nh:
yield ng
ng = next(g)
elif ng > nh:
yield nh
nh = next(h)
else:
yield ng
ng = next(g)
nh = next(h)
def smooth_numbers(primes=(2, 3, 5)):
def _f():
yield 1
mm = times(primes[0], mp[0])
for p, g in zip(primes[1:], mp[1:]):
mm = merge(mm, times(p, g))
yield from mm
m = _f()
*mp, res = itertools.tee(m, len(primes) + 1)
return res
# Generates all 5-smooth numbers in order
# For k-smooth numbers use: tuple(sympy.primerange(1, k+1))
primes = (2, 3, 5)
for n in smooth_numbers(primes):
print(n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment