Dividers

There is a problem like this: how many divisors does the number n have? For example, the number 4 has three divisors: 1, 2 and 4, and the number 6 has four: 1, 2, 3 and 6. Problems of this kind are often encountered at all sorts of litcodes, and the public enthusiastically picks at them. Well, that's right.

The naive solution looks like this:

divisers = [i for i in range(1, n + 1) if n % i == 0]

Its complexity you can live with that. A more subtle solution has a complexity it is based on the idea that, having a divisor numbers less than or equal to you can easily get its conjugate divisor greater (or equal) :

from math import sqrt

divisers = {1, n}
for i in range(2, int(sqrt(n)) + 1):
    if n % i == 0:
        dividers.update([i, n // i])
divisers = sorted(divisers)

The last line is caused by the fact that the checking system (on litcode, for example) wants to obtain an ordered set of divisors. The initial choice of the set as a collection of divisors allows to bypass the situation when – a perfect square, and will not enter into divisors twice.

Is there a better idea? Yes, of course! See:

def factor(n):
    d, p = {}, 2
    while p * p <= n:
        while not n % p:
            d[p] = d.get(p, 0) + 1
            n //= p
        p += 1
    if 1 < n:
        d[n] = 1
    return d

divisers = [1]
for p, q in factor(n).items():
    shift = -len(divisers)
    divisers += (divisers[shift] * p for _ in range(-shift * q))
divisers.sort()

This fragment first declares an auxiliary function factor, which returns all prime factors of n and their powers, which (meaning factors raised to a power) are also factors of n. For example, factor(24) returns {2: 3, 3: 1}, which means 24 == 2 * 2 * 2 * 3.

Then I multiply these prime divisors together in every possible way, and then I get all the divisors of the number both simple and compound. An experienced Pythonista may be confused by the penultimate line, “was that even possible?” Well, I sometimes allow myself to do that, and you decide for yourself whether you can do that)

Is this better idea true? Why all this fuss with simple ones, extra code? After all, if I ran into a big simple one or at least on Where – simple, factor(n) will do all the same iterations, only with greater costs? I think so. Look, every second natural number is even, every third is divisible by 3, etc. Many numbers contain small prime factors, and when they are found, the volume of remaining calculations is reduced many times. Prime numbers, when moving along the natural series in the direction of increase, are becoming less common.

But this multiplication of prime factors, it's also worth something, right? I have a pretty good answer here: I calculated how many divisors there are on average for numbers within the first billion, here's the graph:

There aren't so many of these divisors that you have to worry about calculating them. Just don't think, for God's sake, that I factored this first billion – on the contrary, I simulated this billion!

import numpy as np
import matplotlib.pyplot as plt

N = 1_333_333_333 # я пойду по отрезкам типа 667..1333, среднее 1000, красивое)
sieve = np.ones(N, dtype=np.uint16) # это типа решета Эратосфена, только другое
buf = np.full(N, 2, dtype=np.uint16) # тут буду укапливать кратность делителей,
                                     # произведенную простым делителем 
i = m = 2 # разберёмся с четными
while i < N:
    sieve[i::i] = m
    i *= 2
    m += 1

for p in range(3, N, 2): # и с нечетными
    if sieve[p] == 1:
        pp = p * p
        while pp < N:
            buf[pp::pp] += 1
            pp *= p
        sieve[p::p] *= buf[p::p]
        buf[p::p] = 2

x, y, hi = [], [], N
while 60 < hi: # чтоб не докапываться до мышей, тьфу, слишком мелких отрезков
    lo = (hi + 1) // 2
    x.append((lo + hi) // 2)
    y.append(sum(sieve[lo:hi]) / (hi - lo))
    hi = lo

fig, ax = plt.subplots(figsize=(5, 2.7), layout="constrained")
plt.xscale('log', base=10)
ax.plot(x, y, label="количество делителей числа\n от его порядка, усредненно")
plt.show()

Bonus: 1_102_701_600 has the most divisors in the segment under consideration, 1440. Here is its factor: {2:5, 3:4, 5:2, 7:1, 11:1, 13:1, 17:1}.