1
$\begingroup$

Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố)

Additional conditions:

N is a positive integer in range [1, 2^64 - 1]

K is a positive integer in range [3, 10]

Example: N = 106, K = 3 => res = 105 (3 * 5 * 7)

$\endgroup$
2
  • $\begingroup$ Is there an online judge for this problem? $\endgroup$
    – John L.
    Jun 28, 2022 at 14:54
  • $\begingroup$ For $K\ge4$, it is not unthinkable to precompute and store all products of $K$ successive primes until $2^{64}$. For $K=3$, the table would be large (like $179000$ entries). $\endgroup$
    – user16034
    Mar 25, 2023 at 20:54

3 Answers 3

2
$\begingroup$

It can be checked easily whether the product of the first $K$ primes is larger than $N$. If yes, there is no such number that is not larger than $N$ and is the product of $K$ consecutive primes.

Otherwise, list consecutive primes nears $N^{1/K}$ as $p_1, p_2,\cdots,p_K,p_{K+1}, \cdots, p_{2K-1}$ in increasing order, where $p_K$ is the largest prime not larger than $N^{1/K}$. The wanted largest possible number must be the last product that is not larger than $N$ among the following $K$ products: $$p_1p_2\cdots p_K,\ p_2p_3\cdots p_{K+1},\cdots, p_Kp_{K+1}\cdots p_{2K-1}.$$

In order to list the primes described above easily, we can find all prime numbers not larger than $N^{1/K}+ 340$. I select $340$ since there are more than $10$ primes between $N^{1/K}$ and $N^{1/K}+340$ when $N\lt 2^{64}$ and $K\ge3$. You can use a larger gap such as $2022$ or $152694$ instead; it does not slow down the computation noticeably. Using standard technique, we can find all primes not larger than $(2^{64})^{1/3} + 340$ in less than $0.1$ second.

A straightforward implementation of the approach above in Python could solve the problem within $0.1$ second.

Assume $K\ll N$, an estimate of the time-complexity of the approach above is $O(N^{1/K}\log\log(N^{1/K}))$. Check this Wikipedia article on the time-complexity of the sieve of Eratosthenes that lists all prime numbers up to a given limit.

$\endgroup$
3
  • 1
    $\begingroup$ You'd make some educated guess which interval around N^(1/k) contains k primes. Average distance between primes = log N / k, average length of interval containing k primes = log N, an interval of length 10 log N is very likely to contain the product we are looking for, if not we double the length of the interval and try again. So we use a much smaller sieve, and the work is more proportional to the number of primes whose multiples we remove from the sieve. Let N' = N ^(1/k) then we remove multiples up to N'^(1/2), about N'^(1/2) / log N' of them. $\endgroup$
    – gnasher729
    Jun 28, 2022 at 16:38
  • $\begingroup$ @gnasher729 Thanks for the feedback. I chose the approach in my answer so it is easier to code. A segmented sieve is harder to write. Also, we can check whether a number is prime directly, which leads to another easy approach. $\endgroup$
    – John L.
    Jun 28, 2022 at 16:39
  • $\begingroup$ When $K$ is very small, the method described in gnasher729's comment above runs with $O(\max(N^{1/(2K)}\log\log(N^{1/(2K)}), K\log(N^{3/(2K)})))$ time-complexity. That method should be recommended if the given $N$ is larger. $\endgroup$
    – John L.
    Jun 28, 2022 at 17:22
0
$\begingroup$

Prefill a prime sieve with $2^{64/3}$ entries. This takes $330281$ bytes of storage.

Then for a given $K$, you can start a search from the largest prime below $\sqrt[3]N$, increasingly until you exceed $N$. The products can be computed directly or incrementally (next product from the previous).

$\endgroup$
1
  • 1
    $\begingroup$ You mean the K-th root of N, not the third root. $\endgroup$
    – gnasher729
    Dec 26, 2023 at 16:10
0
$\begingroup$

(Should be read after John L’s answer so I upvoted it to make it come first).

You don’t need to restrict n to be less than $2^{64}$. The primes are around $n^{1/k}$. If this is small enough that you can find primes of that size easily enough, then you can find k+1 consecutive primes so that the product of the first k is not obviously greater than n and the product of the last k is not obviously less.

Calculating both products using floating-point arithmetic has a rounding error, but we can find bounds for that error, and we can often prove that the product of the first k is less than n, and the product of the last k is greater than n.

In other cases, we can prove that one product is less than or greater than n, but not the other one. For example, one product calculated with floating-point arithmetic might compare equal to n. In that case we can use multi-precision arithmetic to divide n by all the primes consecutively and decide.

If the primes are too large, then both products might be too large to decide; this will require some search for the solution.

As an example finding the 10,000 consecutive primes with the largest product less than $10^{100000}$ should find 10000 primes around $10^{10}$ easily.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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