Detailed mathematical approach

Problem Summary

For \(1\le x\le N\), the problem calls \(x\) square root smooth when every prime factor of \(x\) is strictly smaller than \(\sqrt{x}\). The number \(1\) is included as well, because it has no prime factors at all. The goal is to compute the count \(C(N)\) for \(N=10^{10}\) without testing every integer individually.

Mathematical Approach

Let \(P^+(x)\) denote the largest prime factor of \(x\) for \(x\ge 2\). Instead of counting square root smooth integers directly, it is easier to count the complement and subtract from \(N\).

Step 1: Count the Complement

Define

$NS(N)=\#\left\{x\in\{1,\dots,N\}:x\ge 2,\ P^+(x)\ge \sqrt{x}\right\}.$

Then the required answer is simply

$C(N)=N-NS(N).$

So the whole problem becomes: how many integers up to \(N\) have a largest prime factor at least as large as their square root?

Step 2: Unique Representation \(x=pq\)

Take any non-smooth integer \(x\), and let \(p=P^+(x)\) be its largest prime factor. Write

$x=pq.$

Because \(p\ge \sqrt{x}\), we immediately get

$q=\frac{x}{p}\le p.$

Also \(x\le N\) implies

$q\le \left\lfloor\frac{N}{p}\right\rfloor.$

Conversely, suppose \(p\) is prime and

$1\le q\le \min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right).$

Then every prime factor of \(q\) is at most \(q\le p\), so the largest prime factor of \(pq\) is exactly \(p\). Since \(q\le p\), we also have \(p\ge \sqrt{pq}\), so \(pq\) is non-smooth. Therefore every non-smooth number is counted exactly once by a pair \((p,q)\), and

$NS(N)=\sum_{p\le N}\min\left(p,\left\lfloor\frac{N}{p}\right\rfloor\right),$

where the sum runs over primes \(p\).

Step 3: Re-index by the Smaller Factor

The same pairs can be counted by fixing \(q\) first. Because \(q\le p\) and \(pq\le N\), necessarily

$q\le \sqrt{N}.$

For a fixed \(q\), the admissible primes satisfy

$q\le p\le \left\lfloor\frac{N}{q}\right\rfloor.$

Hence

$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right).$

This is the form used by the Python and Java implementations. Once prime counts are known on the relevant arguments, the final summation is immediate.

Step 4: Equivalent Split at \(\sqrt N\)

From the prime-based sum we can also separate the cases \(p\le \sqrt N\) and \(p>\sqrt N\):

$NS(N)=\sum_{p\le \sqrt N}p+\sum_{\sqrt N<p\le N}\left\lfloor\frac{N}{p}\right\rfloor.$

In the second sum the quotient

$k=\left\lfloor\frac{N}{p}\right\rfloor$

is constant on intervals of primes. The relevant block is

$\max\left(\left\lfloor\sqrt N\right\rfloor+1,\left\lfloor\frac{N}{k+1}\right\rfloor+1\right)\le p\le \left\lfloor\frac{N}{k}\right\rfloor,$

so its contribution is

$k\left(\pi\left(\left\lfloor\frac{N}{k}\right\rfloor\right)-\pi\left(\max\left(\left\lfloor\sqrt N\right\rfloor,\left\lfloor\frac{N}{k+1}\right\rfloor\right)\right)\right).$

This is the viewpoint used by the C++ implementation: it groups large primes by equal quotient instead of iterating over every prime one by one.

Step 5: Worked Example for \(N=100\)

Here \(\lfloor\sqrt{100}\rfloor=10\). The small-prime part contributes

$2+3+5+7=17.$

The large-prime blocks are

$\begin{aligned} k=1&:\quad 1\cdot(\pi(100)-\pi(50))=10,\\ k=2&:\quad 2\cdot(\pi(50)-\pi(33))=8,\\ k=3&:\quad 3\cdot(\pi(33)-\pi(25))=6,\\ k=4&:\quad 4\cdot(\pi(25)-\pi(20))=4,\\ k=5&:\quad 5\cdot(\pi(20)-\pi(16))=10,\\ k=7&:\quad 7\cdot(\pi(14)-\pi(12))=7,\\ k=9&:\quad 9\cdot(\pi(11)-\pi(10))=9. \end{aligned}$

The missing values \(k=6\) and \(k=8\) contribute \(0\) because the corresponding intervals contain no primes. Therefore

$NS(100)=17+10+8+6+4+10+7+9=71,$

and thus

$C(100)=100-71=29.$

This matches the checkpoint used by the implementations.

Step 6: Why Prime Counting Solves the Problem

After the transformation above, the original smooth-number question no longer requires factoring every integer up to \(N\). Everything reduces to evaluating \(\pi(x)\) on roughly \(2\sqrt N\) relevant arguments and combining those values with one of the two equivalent summation formulas.

How the Code Works

The C++, Python, and Java implementations all begin with the complement identity \(C(N)=N-NS(N)\). They differ only in how they obtain the needed prime-counting values \(\pi(x)\).

The C++ implementation uses a standard sieve for small values and a cached Lehmer prime-counting method for large arguments. It evaluates the split formula: first add all primes up to \(\lfloor\sqrt N\rfloor\), then process the quotient blocks where \(\left\lfloor N/p\right\rfloor\) is constant and multiply each quotient by the number of primes in that interval.

The Python and Java implementations precompute \(\pi(v)\) simultaneously on the distinct values

$v\in\left\{\left\lfloor\frac{N}{1}\right\rfloor,\left\lfloor\frac{N}{2}\right\rfloor,\dots,\left\lfloor\frac{N}{\lfloor\sqrt N\rfloor}\right\rfloor\right\}\cup\{1,2,\dots,\lfloor\sqrt N\rfloor\}.$

They use the standard combinatorial prime-counting update over all primes up to \(\lfloor\sqrt N\rfloor\), turning an initial table \(v-1\) into exact values of \(\pi(v)\). With those values available, they evaluate

$NS(N)=\sum_{q=1}^{\lfloor\sqrt N\rfloor}\left(\pi\left(\left\lfloor\frac{N}{q}\right\rfloor\right)-\pi(q-1)\right)$

and subtract the result from \(N\).

Complexity Analysis

The mathematical reduction leaves only \(O(\sqrt N)\) relevant \(q\)-values or quotient blocks. The Python and Java implementations store prime-counting data on about \(2\sqrt N\) distinct arguments, so their memory usage is \(O(\sqrt N)\), and their preprocessing is the usual sublinear combinatorial prime-counting pass over those values. The C++ implementation also performs only \(O(\sqrt N)\) outer accumulation steps, with the main cost coming from memoized prime-counting queries. In all three cases the method is vastly faster than scanning every integer up to \(N\) and is easily practical for \(N=10^{10}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=668
2. Largest prime factor: Wikipedia — Largest prime factor
3. Prime-counting function: Wikipedia — Prime-counting function
4. Smooth number: Wikipedia — Smooth number
5. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes