Modified sieve to find count all the divisors from 1 to n in o(n) time

Question

I trying to solve a problem that involves finding the number that has the maximum factors from 1 to $N$ where $N = 10^7$ in just under 2 seconds.

I have implemented a sort of "sieve" that starts from a number $i$ and keeps going through all its multiples and inrementing its factor count by 1. But this approach is still too slow.

I have seen implementation of the Sieve of Eratosthenes in linear time. Can something like this be modified to count the divisors of the numbers in 0(n) time ?

If so how? Also is there any better way to count the factors of all numbers from $1$ to $10^7$ in linear time? Am I missing something?

Let me know if any further information is required.

Answer 1

My answer here is kind of an XY problem answer: you asked for a way to do Y but you said that you want Y to do X. I'm just going to answer how to do X instead.

The basic result here is that if $N=\prod_{i=1}^n p_i^{k_i}$ then $N$ has $\prod_{i=1}^n (k_i+1)$ divisors. This is an easy consequence of the fundamental theorem of arithmetic.

In view of this result, you can think of the original problem in the following way. Set $n$ to be the smallest number with $p_n \# \geq N$ ($p_n \#$ is the product of the first $n$ primes). Now you have a budget of $\log(N)$ to spend. There are $n$ possible "items" (prime factors) to "buy". Each unit of item $i$ costs $\log(p_i)$, where $p_i$ is the $i$th prime. Having $k_i$ of item $i$ gets you a benefit of $\log(k_i+1)$.

Now notice that the prices of the items increase with $i$, but having a lot of the same item gives diminishing returns. As a result, you should choose your $k_i$ to be decreasing (in general not strictly). This requirement alone dramatically reduces the complexity of even a brute force solution to the problem.

In terms of a non-brute force solution, one idea is to build your number greedily. Begin with $k_i \equiv 0$, and now at each stage, choose $i$ to maximize $\frac{\log(k_i+2)-\log(k_i+1)}{\log(p_i)}$. Check whether incrementing $k_i$ by $1$ will violate your constraint. If it doesn't, increment and continue. If it does, then start again and sweep only over those $k_i$ that you are actually allowed to increment. You'll find some "familiar" numbers as you run this procedure, among them 30, 60, 180, and 360.

Another idea is to start from the solution to an easier problem, in which the exponents can be arbitrary nonnegative real numbers. This problem can be solved by Lagrange multipliers. You expect that at least a good solution, if not necessarily an optimal solution, should be given by some rounding of the exponents that you get from this continuous problem.

Answer 2

If you can sieve in linear time, you can sieve up to $\sqrt n$ in square root time. Then you can factor the number very quickly and use the divisor function. This gets you square root time.

Answer 3

It's very easy to prove that any numbers n which have more divisors than any smaller numbers are of the form $n = 2^a 3^b 5^c 7^d 11^e ...$ with $a ≥ b ≥ c ≥ d ≥ e ...$ (and the number of divisors is $(a+1)(b+1)(c+1)(d+1)(e+1)...$)

So there are much fewer numbers n than $10^7$ that you need to check, and you can easily calculate their numbers of divisors. Without any sieve.

Remember: Nobody asked you to find the numbers of divisors of all numbers ≤ $10^7$. You were asked to find the one number with the most divisors only.