Solution

Answer: 1096883702440585

Let

$$p=\prod_{\substack{q\text{ prime}\ q<190}} q.$$

We seek the largest divisor of $p$ not exceeding $\sqrt p$. Since $p$ is squarefree, every divisor corresponds to choosing a subset of the primes below $190$.

Thus the problem becomes:

Choose a subset of the primes below $190$ whose product is as large as possible while remaining $\le \sqrt p$.

Equivalently, taking logarithms:

$$\log d=\sum_{q\in S}\log q$$

must be as close as possible to

$$\frac12 \log p.$$

This is a classic balanced subset-product / knapsack problem, and the correct approach is a meet-in-the-middle search.

1. Mathematical analysis

The primes below $190$ are

$$2,3,5,7,\dots,181.$$

There are $42$ such primes, so brute force over all subsets would require checking

$$2^{42}\approx 4.4\times 10^{12}$$

subsets — impossible directly.

Reformulation

Let

$$p=\prod_{i=1}^{42} p_i.$$

Every divisor of $p$ has the form

$$d=\prod_{i\in S} p_i$$

for some subset $S$.

We want

$$d\le \sqrt p$$

and $d$ maximal.

Taking logs:

$$\log d=\sum_{i\in S}\log p_i.$$

Since

$$\log \sqrt p=\frac12\sum_{i=1}^{42}\log p_i,$$

we want a subset sum of the logarithms as close as possible to half the total, without exceeding it.

2. Meet-in-the-middle

Split the primes into two halves:

left half $L$
right half $R$

Each half has about $21$ primes.

For each subset of $L$, compute:

its logarithmic sum
its exact product

Likewise for $R$.

Each side has only

$$2^{21}=2,097,152$$

subsets, which is manageable.

Key idea

Suppose a left subset has log-sum $x$.

Then the right subset must satisfy

$$y \le T-x$$

where

$$T=\frac12\log p.$$

So for each left subset, we binary-search the right subsets for the largest feasible $y$.

The corresponding exact products are multiplied, and we keep the largest valid product.

3. Python implementation

from math import log
from bisect import bisect_right

# Generate primes below 190
def primes_below(n):
    sieve = [True] * n
    sieve[0] = sieve[1] = False

    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i * i, n, i):
                sieve[j] = False

    return [i for i, v in enumerate(sieve) if v]

primes = primes_below(190)

# Total logarithmic target
total_log = sum(log(p) for p in primes)
target = total_log / 2

# Split primes into two halves
mid = len(primes) // 2
A = primes[:mid]
B = primes[mid:]

# Enumerate all subset products and log sums
def subset_data(arr):
    n = len(arr)
    out = []

    for mask in range(1 << n):
        prod = 1
        s = 0.0

        for i in range(n):
            if mask & (1 << i):
                prod *= arr[i]
                s += log(arr[i])

        out.append((s, prod))

    return out

left = subset_data(A)
right = subset_data(B)

# Sort right subsets by logarithmic sum
right.sort()

right_logs = [x[0] for x in right]

best = 0

# For each left subset, binary search best compatible right subset
for ls, lp in left:

    remain = target - ls

    idx = bisect_right(right_logs, remain) - 1

    if idx >= 0:
        rp = right[idx][1]
        candidate = lp * rp

        if candidate > best:
            best = candidate

# Required modulo
answer = best % (10**16)

print(answer)

4. Code walkthrough

Prime generation

primes_below(190)

creates all primes $<190$.

Target

target = total_log / 2

represents

$$\log(\sqrt p).$$

Subset enumeration

For each subset we store:

(log_sum, exact_product)

The logarithm is used for efficient comparison; the exact product is used to recover the true divisor.

Binary search

The right-half subsets are sorted by log-sum.

For a left subset with log $ls$, we need

$$rs \le target-ls.$$

Using:

bisect_right(right_logs, remain)

we instantly find the largest feasible right subset.

5. Small-example verification

For the example

$$3102 = 2\cdot3\cdot11\cdot47,$$

we have

$$\sqrt{3102}\approx 55.7.$$

Divisors below this are

$$1,2,3,6,11,22,33,47.$$

Largest is $47$, matching the statement.

The algorithm reproduces this behavior exactly.

6. Final verification

The result should:

be less than $10^{16}$ after reduction,
correspond to a divisor very close to $\sqrt p$,
arise from a balanced partition of the logarithms of the primes below $190$.

Running the computation gives:

$$\boxed{1096883702440585}$$

Answer: 1096883702440585

Project Euler Problem 266