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 > 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 < 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] > 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 > 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 > 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.