Listing all numbers that are more composite than every number less than it This code is my first naive attempt at writing a program that lists all numbers less than a given value that are more composite (have more divisors) than any number less than that number (for example, 12 is more composite than any number less than it).

def composite_count(limit):
    answer = []
    most_divisors = 0
    for i in range(limit):
        tally = 0
        for j in range(i):
            if not (i + 1) % (j + 1):
                tally += 1
        if tally &gt; most_divisors:
            most_divisors = tally
            answer.append((i + 1))
    return answer


After running the program a few times, I started to see some patterns like the fact that all of the listed answers were even, that all answers greater than 12 are divisible by 12, or that all answers greater than 60 are divisible by 60. I also ran some tests involving prime factorization and found that although the more composite numbers do not always have more prime factors, the sum of their prime factors are always larger. Despite all this information I was not able to figure out any changes to the algorithm that would create significant time saves.

Can someone please help me make this code meaningfully faster?
The biggest thing that will gain you performance is breaking this up into two functions, one that gets the prime factor list of a number, and another that computes the total number of factors from a prime factorization (using This method). Using this, we get the following

def generate_primes(end):
    primes = []
    for i in range(2, end):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            primes.append(i)
    return primes

def prime_power_generator(x, primes):
    # Most of these steps will not be run.
    # The largest prime iterated to will be the largest prime factor of x
    # (not including x)
    for p in primes:
        if x % p == 0:
            times = 0
            while x % p == 0:
                times += 1
                x //= p
            yield times
            if x == 1:
                return

def number_of_factors_with_help(x, primes):
    answer = 1
    for power in prime_power_generator(x, primes):
        answer *= power+1
    return answer

def better_composite_count(limit):
    answer = [1]
    primes = generate_primes(int(limit**.5)+1)
    most_divisors = 0
    for x in range(2,limit+1,2):
        num_divisors = number_of_factors_with_help(x, primes)
        if num_divisors &gt; most_divisors:
            most_divisors = num_divisors
            answer.append(x)
    return answer


By limit=10**5, this is clearly superior, taking .02 seconds, instead of 50 for the OP. However, there is a better way. These numbers have several properties that allow much more a much faster search. For any highly compoite n, the prime factorization of n:


contains consecutive primes starting with 2
with decreasing frequency
the largest prime factor has frequency 1 (except for 4 and 36)


There are very few numbers that satisfy these constraints, and computing them by their prime factorization means we don't have to factor them later. These insights leads to the following code:

def gen_primes():
    D = {}
    q = 2  # first integer to test for primality.

    while True:
        if q not in D:
              # not marked composite, must be prime  
              yield q 

              #first multiple of q not already marked
              D[q * q] = [q] 
        else:
              for p in D[q]:
                    D.setdefault(p + q, []).append(p)
              # no longer need D[q], free memory
              del D[q]
        q += 1

def num_factors(prime_factorization):
    ans = 1
    for power in prime_factorization:
        ans *= power+1
    return ans

def composite_candidates(primes, limit, factors=(1,), num=2, candidates=None, idx=0):
    if candidates == None:
        candidates={1:1, 4:3, 36:9}
    if num &lt; limit:
        if factors[-1] == 1:
            candidates[num] = num_factors(factors)
        # current exponent must be equal or less than previous one
        if len(factors) == 1 or factors[-2] &gt; factors[-1]:
            # we either stay with current prime and increase exponent
            composite_candidates(primes,
                                 limit, 
                                 factors[:-1] + (factors[-1] + 1,), 
                                 num * primes[idx], 
                                 candidates, 
                                 idx)
        # or move to next prime
        idx += 1
        composite_candidates(primes, 
                             limit, 
                             factors + (1,),
                             num * primes[idx], 
                             candidates, 
                             idx)
    return candidates

def best_composite_count(limit):
    # primes up to the largest possible in a highly composite number
    primes = []
    prime_product = 1
    for prime in gen_primes():
        primes.append(prime)
        prime_product *= prime
        if prime_product &gt; limit:
            break

    # generate numbers, and number of factors for numbers that might work
    candidates = composite_candidates(primes, limit)
    composites = []
    most_divisors = 0
    # its important that they are sorted to know current highest number of divisors
    for num in sorted(candidates.keys()):
        num_divisors = candidates[num]
        if num_divisors &gt; most_divisors:
            composites.append(num)
            most_divisors = num_divisors
    return composites


This yields another similarly massive increase over the previous, and can sieve up to 10^30 in less than 5 seconds.