0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – reuns Dec 19 '17 at 19:03
  • 1
    $\begingroup$ If you need a table of primes for something, an internet search turned up a result already created for $K=12$. $\endgroup$ – John Dec 19 '17 at 20:22
  • $\begingroup$ Link to data dump - I just searched "table of primes"; I assume you can do the same? $\endgroup$ – John Dec 19 '17 at 20:29
  • $\begingroup$ @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$. $\endgroup$ – reuns Dec 19 '17 at 20:31
  • $\begingroup$ 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$. $\endgroup$ – reuns Dec 19 '17 at 20:53
0
$\begingroup$

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;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.