# Table of biggest prime factor of every integer in 2 … 10^K

How would you precalculate a big table of the biggest prime factor of every integer in $2 \dots 10^K$? The goal would be to do it once for all, save it to a file, and reload it later for fast computations (involving smooth numbers). I tried with R:

library(gmp)    # the fastest factorization I've found on R, faster than number theory package "numbers"
v = sapply(2:10^7, function(x) as.integer(max(factorize(x))))
save(v, file="bpf.dat")


allowing later to load it with: load("bpf.dat").

But this is very slow (35 seconds for $K=6$, 390 seconds for $K=7$ , etc.). Which number-theoretic idea could be used to generate such a table faster?

Note: I've already looked at https://oeis.org/A006530.
Note2: This question has been removed in mathoverflow (because too obvious), but I wanted to post here question+answer thanks to the helpful comments that were provided.

• The algorithm to generate $\text{Lpf}(n) = \sup_{p | n} p$ for $n \in 1 \ldots N$ is the Eratosthenes sieve which is $\mathcal{O}(C \sum_{p \le N} \lfloor N / p \rfloor) = \mathcal{O}(N \log \log N \ C)$ in time and $\mathcal{O}(N C)$ in memory, where $C \approx \log_2 N$ is the size of your representation of $n$ in memory. Clearly you can't do much better. – reuns Dec 19 '17 at 19:03
• If you need a table of primes for something, an internet search turned up a result already created for $K=12$. – John Dec 19 '17 at 20:22
• Link to data dump - I just searched "table of primes"; I assume you can do the same? – John Dec 19 '17 at 20:29
• @Basj Do you understand the asymptotic complexity I provided ? The main point is $\sum_{p \le N} \frac{1}{p} \sim \log \log N$ (Mertens theorem). But as a first estimate, you may say $\sum_{p \le N} \frac{1}{p}\le \sum_{n \le N} \frac{1}{n} \sim \log N$. – reuns Dec 19 '17 at 20:31
• The prime number theorem yields with partial summation $\sum_{p \le N} f(p) \sim \sum_{n \le N} \frac{f(n)}{\log n}$ for any $f(n) = n^a , a \ge -1$. – reuns Dec 19 '17 at 20:53

## 1 Answer

As mentioned in a comment of a now-deleted question, a modification of the sieve of Eratosthenes will produce this information very quickly, almost in linear time. Here is some C code to do it:

#include <iostream>
#include <vector>

const int MAX = 1000000000;

int main() {
std::vector<int> largest(MAX);

for (int i = 2; i < MAX; ++i)
largest[i] = i;

for (int i = 2; i < MAX; ++i)
if (largest[i] == i)
for (int j = i+i; j < MAX; j += i)
largest[j] = i;

for (int i = 2; i < MAX; ++i)
std::cout << largest[i] << std::endl;
}