Project Euler

Eight Divisors

The eight divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24. The ten numbers not exceeding 100 having exactly eight divisors are 24, 30, 40, 42, 54, 56, 66, 70, 78, and 88. Let f(n) denote the count...

Source sync Apr 19, 2026

Problem #0501

Level Level 12

Solved By 1,606

Languages C++, Python

Answer 197912312715

Length 480 words

number_theorylinear_algebrabrute_force

The eight divisors of $24$ are $1, 2, 3, 4, 6, 8, 12$ and $24$. The ten numbers not exceeding $100$ having exactly eight divisors are $24, 30, 40, 42, 54, 56, 66, 70, 78$ and $88$.

Let $f(n)$ be the count of numbers not exceeding $n$ with exactly eight divisors.

You are given $f(100) = 10$, $f(1000) = 180$ and $f(10^6) = 224427$.

Find $f(10^{12})$.

Problem 501: Eight Divisors

Mathematical Development

Theorem 1 (Divisor Count Formula). Let $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ be the canonical prime factorization of a positive integer $n > 1$ . Then the number of positive divisors of $n$ is

\tau(n) = \prod_{i=1}^{k} (a_i + 1).

Proof. Every divisor of $n$ has the form $d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$ where $0 \le b_i \le a_i$ for each $1 \le i \le k$ . By the fundamental theorem of arithmetic, distinct exponent tuples $(b_1, \ldots, b_k)$ yield distinct divisors. The number of valid tuples is $\prod_{i=1}^{k}(a_i + 1)$ by the multiplication principle. $\square$

Lemma 1 (Classification of integers with $\tau(n) = 8$ ). A positive integer $n$ satisfies $\tau(n) = 8$ if and only if $n$ belongs to exactly one of the following three families:

Type A: $n = p^7$ for some prime $p$ .
Type B: $n = p^3 q$ for distinct primes $p$ and $q$ .
Type C: $n = pqr$ for distinct primes $p < q < r$ .

Proof. We require $\prod_{i=1}^{k}(a_i + 1) = 8$ . Since each factor $a_i + 1 \ge 2$ , we seek all multiplicative compositions of $8 = 2^3$ into parts $\ge 2$ . The only such compositions (up to reordering) are:

$8 = 8$ : a single exponent $a_1 = 7$ , yielding $n = p^7$ .
$8 = 4 \cdot 2$ : two exponents $(a_1, a_2) = (3, 1)$ , yielding $n = p^3 q$ with $p \ne q$ .
$8 = 2 \cdot 2 \cdot 2$ : three exponents $(a_1, a_2, a_3) = (1, 1, 1)$ , yielding $n = pqr$ with distinct primes.

No other multiplicative partition of 8 into factors $\ge 2$ exists. The three families are mutually exclusive since the multiset of exponents uniquely determines the family. $\square$

Theorem 2 (Counting Formula). Let $N = 10^{12}$ and let $\pi(x)$ denote the prime-counting function. Then

f(N) = C_1 + C_2 + C_3

where:

C_1 = \pi\!\left(\lfloor N^{1/7} \rfloor\right),

C_2 = \sum_{\substack{p \text{ prime} \\ p^3 < N}} \left[\pi\!\left(\left\lfloor \frac{N}{p^3} \right\rfloor\right) - \mathbf{1}_{[p^4 \le N]}\right],

C_3 = \sum_{\substack{p \text{ prime}}} \;\sum_{\substack{q \text{ prime} \\ p < q \\ pq^2 \le N}} \left[\pi\!\left(\left\lfloor \frac{N}{pq} \right\rfloor\right) - \pi(q)\right].

Proof. We count each family from Lemma 1 separately.

Case 1 (Type A). The condition $p^7 \le N$ is equivalent to $p \le N^{1/7}$ . Since $p$ must be prime, the count is $C_1 = \pi(\lfloor N^{1/7} \rfloor)$ .

Case 2 (Type B). Fix a prime $p$ with $p^3 < N$ . We count primes $q \le N/p^3$ with $q \ne p$ . The number of primes $q \le N/p^3$ is $\pi(\lfloor N/p^3 \rfloor)$ . Among these, $q = p$ is included if and only if $p \le N/p^3$ , i.e., $p^4 \le N$ . Hence we subtract the indicator $\mathbf{1}_{[p^4 \le N]}$ to exclude the case $q = p$ (which would give $n = p^4$ with $\tau(n) = 5 \ne 8$ ). Note that the pair $(p, q)$ and $(q, p)$ with $p \ne q$ yield the same product $p^3 q$ only if $p$ and $q$ swap roles, but $p^3 q \ne q^3 p$ when $p \ne q$ , so these are distinct integers counted under different values of the outer summation variable. Hence no double-counting occurs.

Case 3 (Type C). We impose the ordering $p < q < r$ to avoid overcounting. For each prime pair $(p, q)$ with $p < q$ , we require prime $r$ satisfying $q < r \le N/(pq)$ . The count of such $r$ is $\pi(\lfloor N/(pq) \rfloor) - \pi(q)$ , which is nonnegative precisely when $pq^2 \le N$ (since the smallest valid $r$ exceeds $q$ , so we need $N/(pq) > q$ ).

The three families are mutually exclusive by Lemma 1, so $f(N) = C_1 + C_2 + C_3$ . $\square$

Editorial

We case 2: n = p^3 * q, p != q. Finally, case 3: n = p * q * r with p < q < r.

Pseudocode

Case 1: n = p^7
Case 2: n = p^3 * q, p != q
Case 3: n = p * q * r with p < q < r

Complexity Analysis

Time. The dominant cost is constructing the Lucy Hedgehog prime-counting tables, which runs in $O(N^{2/3} / \log N)$ time. The enumeration in Case 2 iterates over $O(N^{1/3} / \log N)$ primes, each requiring an $O(1)$ table lookup. The double enumeration in Case 3 iterates over $O(N^{2/3} / \log^2 N)$ pairs (by the prime counting estimate $\pi(x) \sim x / \log x$ ), each with an $O(1)$ lookup. Thus the total time is $O(N^{2/3})$ .

Space. The Lucy Hedgehog method maintains two arrays of size $O(\sqrt{N})$ , plus the sieve of primes up to $\sqrt{N}$ . Total space is $O(N^{1/2})$ .

Answer

\boxed{197912312715}

C++ project_euler/problem_501/solution.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// Lucy Hedgehog's prime counting function
// Returns pi(x) for any x, after preprocessing for values up to N
struct PrimeCount {
    ll N;
    int sqrtN;
    vector<ll> small, large;
    vector<int> primes;
    vector<bool> sieve;

    void init(ll n) {
        N = n;
        sqrtN = (int)sqrt((double)n);
        while ((ll)sqrtN * sqrtN > n) sqrtN--;
        while ((ll)(sqrtN + 1) * (sqrtN + 1) <= n) sqrtN++;

        // Sieve primes up to sqrtN
        sieve.assign(sqrtN + 1, true);
        sieve[0] = sieve[1] = false;
        primes.clear();
        for (int i = 2; i <= sqrtN; i++) {
            if (sieve[i]) {
                primes.push_back(i);
                for (ll j = (ll)i * i; j <= sqrtN; j += i)
                    sieve[j] = false;
            }
        }

        // small[i] = count of primes <= i, for i = 0..sqrtN
        // large[i] = count of primes <= N/i, for i = 1..sqrtN
        small.assign(sqrtN + 1, 0);
        large.assign(sqrtN + 1, 0);

        for (int i = 1; i <= sqrtN; i++) {
            small[i] = i - 1; // initially, all numbers >= 2
            large[i] = N / i - 1;
        }

        for (int p : primes) {
            ll pp = (ll)p * p;
            if (pp > N) break;

            ll pcnt_prev = small[p - 1]; // pi(p-1)

            for (int i = 1; i <= sqrtN && (ll)i * pp <= N; i++) {
                ll d = (ll)i * p;
                if (d <= sqrtN)
                    large[i] -= large[d] - pcnt_prev;
                else
                    large[i] -= small[N / d] - pcnt_prev;
            }

            for (int i = sqrtN; i >= pp; i--) {
                small[i] -= small[i / p] - pcnt_prev;
            }
        }
    }

    ll count(ll x) {
        if (x <= 0) return 0;
        if (x <= sqrtN) return small[x];
        ll idx = N / x;
        if (idx <= sqrtN) return large[idx];
        // Fallback -- shouldn't happen if x is of form N/k
        return 0;
    }
};

int main() {
    ll N = 1000000000000LL; // 10^12

    PrimeCount pc;
    pc.init(N);

    ll ans = 0;

    // Case 1: p^7 <= N => p <= N^(1/7) ~ 51
    {
        int lim = (int)pow((double)N, 1.0 / 7.0);
        while ((ll)pow(lim + 1, 7) <= N) lim++;
        while ((ll)pow(lim, 7) > N) lim--;
        // Count primes up to lim
        for (int p : pc.primes) {
            if (p > lim) break;
            ll val = 1;
            bool ok = true;
            for (int j = 0; j < 7; j++) {
                val *= p;
                if (val > N) { ok = false; break; }
            }
            if (ok && val <= N) ans++;
        }
    }

    // Case 2: p^3 * q <= N, p != q
    {
        // Sieve primes up to cbrt(N) ~ 10^4 for p
        int plim = (int)cbrt((double)N);
        while ((ll)(plim + 1) * (plim + 1) * (plim + 1) <= N) plim++;

        // We need all primes up to plim (and beyond for q)
        // Use pc.primes for small primes, and pc.count for pi(x)
        int sieve_lim = max(plim + 1, pc.sqrtN);
        vector<bool> sv(sieve_lim + 1, true);
        sv[0] = sv[1] = false;
        for (int i = 2; (ll)i * i <= sieve_lim; i++)
            if (sv[i])
                for (int j = i * i; j <= sieve_lim; j += i)
                    sv[j] = false;

        for (int p = 2; p <= plim; p++) {
            if (!sv[p]) continue;
            ll p3 = (ll)p * p * p;
            if (p3 >= N) break;
            ll qlim = N / p3;
            ll cnt = pc.count(qlim);
            // Subtract 1 if p <= qlim (to remove q = p)
            if (p <= qlim) cnt--;
            ans += cnt;
        }
    }

    // Case 3: p * q * r <= N, p < q < r, all distinct primes
    {
        int sieve_lim = pc.sqrtN;
        vector<bool> sv(sieve_lim + 1, true);
        sv[0] = sv[1] = false;
        for (int i = 2; (ll)i * i <= sieve_lim; i++)
            if (sv[i])
                for (int j = i * i; j <= sieve_lim; j += i)
                    sv[j] = false;

        vector<int> all_primes;
        for (int i = 2; i <= sieve_lim; i++)
            if (sv[i]) all_primes.push_back(i);

        for (int i = 0; i < (int)all_primes.size(); i++) {
            ll p = all_primes[i];
            if (p * p * p >= N) break; // need q > p, r > q, so p*q*r > p^3
            // Actually p*(p+1)*(p+2) >= p^3 approximately

            for (int j = i + 1; j < (int)all_primes.size(); j++) {
                ll q = all_primes[j];
                ll pq = p * q;
                if (pq * (q + 1) > N) break; // r > q needed
                ll rlim = N / pq;
                // r > q, r prime
                ll cnt = pc.count(rlim) - pc.count(q);
                if (cnt > 0) ans += cnt;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Python project_euler/problem_501/solution.py

def solve():
    N = 10**12

    # Compute floor(sqrt(N)) precisely
    sqrtN = int(N**0.5)
    while sqrtN * sqrtN > N:
        sqrtN -= 1
    while (sqrtN + 1) * (sqrtN + 1) <= N:
        sqrtN += 1

    # Lucy Hedgehog prime counting method
    # small[i] = pi(i) for i <= sqrtN
    # large[i] = pi(N // i) for 1 <= i <= sqrtN
    small = list(range(-1, sqrtN + 1))
    small[0] = 0
    large = [0] * (sqrtN + 1)
    for i in range(1, sqrtN + 1):
        large[i] = N // i - 1

    sieve = [True] * (sqrtN + 1)
    primes = []

    for p in range(2, sqrtN + 1):
        if not sieve[p]:
            continue
        primes.append(p)
        if p * p > N:
            continue
        pcnt = small[p - 1]
        for i in range(1, sqrtN + 1):
            if i * p * p > N:
                break
            d = i * p
            if d <= sqrtN:
                large[i] -= large[d] - pcnt
            else:
                large[i] -= small[N // d] - pcnt
        for i in range(sqrtN, p * p - 1, -1):
            small[i] -= small[i // p] - pcnt

    def pi(x):
        if x <= 0:
            return 0
        if x <= sqrtN:
            return small[x]
        idx = N // x
        if idx <= sqrtN:
            return large[idx]
        return 0

    ans = 0

    # Case 1: p^7 <= N
    for p in primes:
        if p**7 > N:
            break
        ans += 1

    # Case 2: p^3 * q <= N, p != q
    for p in primes:
        p3 = p * p * p
        if p3 >= N:
            break
        qlim = N // p3
        cnt = pi(qlim)
        if p <= qlim:
            cnt -= 1
        ans += cnt

    # Case 3: p < q < r, p*q*r <= N
    for i, p in enumerate(primes):
        if p * p * p >= N:
            break
        for j in range(i + 1, len(primes)):
            q = primes[j]
            pq = p * q
            if pq * (q + 1) > N:
                break
            rlim = N // pq
            cnt = pi(rlim) - pi(q)
            if cnt > 0:
                ans += cnt

    print(ans)

solve()