Prime Scheduler

prime_scheduler.py

# Prime Number Scheduler
# factoring number N has complexity < O(N log N)

# factorizes numbers sequentially with amortized complexity O(1) per number
# written by Leonard Ritter, 2024

schedule = {}
x = 2
while x < 1000000:
    # get all factors scheduled for this number
    factors = schedule.get(x, [])
    # print number and its unique factors
    # once factors are known, their exponents can be computed in O(log x),
    # but we won't do that here.
    print(x, factors)
    if len(factors) == 0: # found a new prime
        # schedule for next occurence
        schedule.setdefault(x * 2, []).append(x)
    else:
        # schedule prime factors at their next occurence
        for c in factors:
            schedule.setdefault(x + c, []).append(c)
        # we're done with this one, free memory
        del schedule[x]
    x += 1