Detailed mathematical approach

Problem Summary

We want the number of integers \(x\le n\) that have exactly eight positive divisors. For the target scale \(n=10^{12}\), testing each integer separately would be far too slow, so the solution classifies every valid number by its prime-factor pattern and turns the problem into a small set of prime-counting formulas.

Mathematical Approach

Let

$f(n)=\#\{x\in \mathbb{Z}_{>0}:x\le n,\ d(x)=8\},$

where \(d(x)\) is the divisor-counting function. If

$x=\prod_i p_i^{a_i},$

then

$d(x)=\prod_i (a_i+1).$

So the entire problem is to find all exponent patterns whose contribution to \(d(x)\) is exactly \(8\), and then count how many numbers of each pattern lie below \(n\).

Step 1: Classify all numbers with exactly eight divisors

The multiplicative partitions of \(8\) are

$8,\qquad 4\cdot 2,\qquad 2\cdot 2\cdot 2.$

Therefore every integer with exactly eight divisors has one of the three mutually exclusive shapes

$x=p^7,\qquad x=p^3q,\qquad x=pqr,$

where \(p,q,r\) are primes, \(p\ne q\) in the middle case, and \(p\lt q\lt r\) in the last case. No other factorization type is possible, because any other exponent list would make \(\prod (a_i+1)\neq 8\).

Step 2: Count the three-prime case \(pqr\)

Fix ordered primes \(p\lt q\lt r\) with

$pqr\le n.$

For a fixed pair \((p,q)\), the third prime must satisfy

$q\lt r\le \left\lfloor\frac{n}{pq}\right\rfloor.$

Hence the number of admissible \(r\) values is

$\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q),$

where \(\pi(x)\) is the prime-counting function. Also, once \(q^2>n/p\), even the smallest possible \(r\) is too large, so \(q\) only needs to run up to \(\left\lfloor\sqrt{n/p}\right\rfloor\). This gives

$A(n)=\sum_{\substack{p\lt q\\ pq^2\le n}}\left(\pi\!\left(\left\lfloor\frac{n}{pq}\right\rfloor\right)-\pi(q)\right).$

Step 3: Count the mixed-power case \(p^3q\)

Now fix a prime \(p\). Any prime \(q\) with

$q\le \left\lfloor\frac{n}{p^3}\right\rfloor$

produces a candidate \(p^3q\le n\). If we temporarily ignore the restriction \(q\ne p\), the contribution from this \(p\) is simply \(\pi(\lfloor n/p^3\rfloor)\). Summing over all possible base primes yields the raw count

$B_{\mathrm{raw}}(n)=\sum_{p\le \lfloor \sqrt[3]{n}\rfloor}\pi\!\left(\left\lfloor\frac{n}{p^3}\right\rfloor\right).$

This is exactly the quantity the implementation accumulates before correcting the bad diagonal case.

Step 4: Correct the overcount and add the \(p^7\) family

The raw sum \(B_{\mathrm{raw}}(n)\) incorrectly includes the choice \(q=p\). That choice gives

$p^3q=p^4,$

and \(p^4\) has only

$d(p^4)=5$

divisors, not \(8\). This invalid term appears exactly when

$p^4\le n,$

so the number of bad terms is

$\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$

Therefore the correct count for the \(p^3q\) family is

$B(n)=B_{\mathrm{raw}}(n)-\pi\!\left(\left\lfloor n^{1/4}\right\rfloor\right).$

The remaining family is \(p^7\le n\), whose contribution is

$C(n)=\pi\!\left(\left\lfloor n^{1/7}\right\rfloor\right).$

Putting the three disjoint cases together, we obtain

$\boxed{f(n)=A(n)+B(n)+C(n).}$

Worked Example: \(n=100\)

For the \(pqr\) family, only \(p=2\) contributes. With \((p,q)=(2,3)\), we get

$\pi\!\left(\left\lfloor\frac{100}{6}\right\rfloor\right)-\pi(3)=\pi(16)-\pi(3)=6-2=4,$

corresponding to \(30,42,66,78\). With \((p,q)=(2,5)\), we get

$\pi\!\left(\left\lfloor\frac{100}{10}\right\rfloor\right)-\pi(5)=\pi(10)-\pi(5)=4-3=1,$

which gives \(70\). Hence

$A(100)=5.$

For the \(p^3q\) family, the raw count is

$B_{\mathrm{raw}}(100)=\pi(12)+\pi(3)=5+2=7.$

The invalid choices \(q=p\) are counted by

$\pi\!\left(\left\lfloor 100^{1/4}\right\rfloor\right)=\pi(3)=2,$

so

$B(100)=7-2=5.$

These five numbers are \(24,40,54,56,88\). Finally, \(100\lt 2^7\), so

$C(100)=0.$

Therefore

$f(100)=5+5+0=10,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations first compute exact integer square, cube, and seventh roots, with small corrective adjustments so every boundary case is handled safely. They then sieve all primes up to \(\lfloor\sqrt{n}\rfloor\). That range is enough for explicit iteration, because every prime that appears in the outer loops lies at most in that interval.

Next, the implementation builds a combinatorial prime-counting structure on two domains: direct arguments up to \(\sqrt{n}\), and quotient arguments of the form \(\lfloor n/i\rfloor\). After a prime-by-prime update pass, this structure can answer every needed value of \(\pi(x)\) in constant time.

With those prime counts available, the implementation evaluates the same three contributions as the mathematics: prime pairs for the \(pqr\) family, the raw sum for \(p^3q\), the subtraction of the forbidden \(p^4\) terms, and finally the \(p^7\) contribution. The sum of those parts is the final answer.

Complexity Analysis

Let \(v=\lfloor\sqrt{n}\rfloor\). The sieve and the prime-counting preprocessing use \(O(v)\) memory and about \(O(v\log\log v)\) arithmetic on the explicitly sieved range. The \(p^3q\) stage iterates over primes \(p\le n^{1/3}\), so it requires only \(O(\pi(n^{1/3}))\) prime-count queries.

The dominant work is the \(pqr\) stage, which visits each prime pair \((p,q)\) satisfying \(p\lt q\) and \(pq^2\le n\). Its loop count is

$O\!\left(\sum_{p\le n^{1/3}}\pi\!\left(\sqrt{\frac{n}{p}}\right)\right),$

and each visit performs only \(O(1)\) table lookups. In practice this is vastly smaller than scanning all integers up to \(n\), and it is easily fast enough for \(n=10^{12}\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=501
2. Divisor function: Wikipedia — Divisor function
3. Prime-counting function: Wikipedia — Prime-counting function
4. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
5. Fundamental theorem of arithmetic: Wikipedia — Fundamental theorem of arithmetic