Problem 668: Square Root Smooth Numbers

Mathematical Analysis

Definition Formalization

A number $n > 1$ is square root smooth if its largest prime factor $P^+(n) < \sqrt{n}$, i.e., $P^+(n)^2 < n$. By convention, $n = 1$ is square root smooth (it has no prime factors).

Key Observation

The complementary set (numbers that are NOT square root smooth, excluding 1) consists of numbers $n \le N$ where $n$ has a prime factor $p \ge \sqrt{n}$. Any such $n$ can be written as $n = p \cdot m$ where $p$ is prime, $p \ge \sqrt{n}$, and $m = n/p \le \sqrt{n} < p$. Since $m < p$ and $p$ is the largest prime factor, $m$ must be a positive integer with all prime factors $< p$.

Counting Strategy

Total square root smooth numbers $= N - |\{n \le N : n > 1 \text{ and } n \text{ is not square root smooth}\}|$.

Equivalently, let $f(N)$ count square root smooth numbers $\le N$:

A cleaner approach: count numbers NOT square root smooth. Each such $n$ has a unique representation $n = p \cdot m$ where $p = P^+(n)$ (largest prime factor) and $1 \le m \le N/p$, with all prime factors of $m$ less than $p$.

So the count of non-square-root-smooth $n \le N$ (excluding 1) is:

Wait — let’s be more careful. A number $n > 1$ is NOT square root smooth iff $P^+(n) \ge \sqrt{n}$, i.e., $P^+(n)^2 \ge n$.

We can split into two cases:

1. $n = p$ is prime ($m = 1$): there are $\pi(N)$ such numbers.
2. $n = p \cdot m$ with $m > 1$, $p = P^+(n)$, and $p^2 \ge n$, so $p \ge \sqrt{n} > \sqrt{m \cdot p}$, giving $p > m$. All prime factors of $m$ are $< p$, and $m \cdot p \le N$.

For case 2, for each prime $p$, $m$ ranges over integers $2 \le m \le N/p$ with $m < p$ and all prime factors of $m$ less than $p$. Since $m < p$ and $p$ is prime, the condition “all prime factors of $m$ less than $p$” is automatic. So the count for case 2 is:

Thus:

Simplify: For $p \le \sqrt{N}$: $\min(p-1, N/p) = p-1$, contributing $p - 2$. For $\sqrt{N} < p \le N/2$: $\min(p-1, N/p) = \lfloor N/p \rfloor$, contributing $\lfloor N/p \rfloor - 1$.

Editorial

A positive integer n is square root smooth if all prime factors < sqrt(n). Count such n <= N = 10^10 (including 1). n is NOT square root smooth iff it has a prime factor p >= sqrt(n). We count the complement. For each n > 1, let p = P+(n) be largest prime factor. n is not smooth iff p^2 >= n. Write n = p * m where m = n/p. Then m < p (from p^2 >= n = pm => p > m, actually p >= m, and if p = m then n = p^2, P+(n) = p = sqrt(n), not strictly less). Case A: m = 1, i.e., n = p is prime. Count = pi(N). Case B: m >= 2, m < p, all prime factors of m < p (auto since m < p). For each prime p: m from 2 to min(p-1, N//p). Number of valid m = min(p-1, N//p) - 1. Answer = 1 + N - pi(N) - sum over primes p of (min(p-1, N//p) - 1) where the sum is over primes 2 <= p <= N//2. But wait: for p = 2, min(p-1, N//p) - 1 = min(1, 5*10^9) - 1 = 0. That’s correct since m must be >= 2 and < 2, impossible. For p = 3: min(2, N//3) - 1 = 1. So m = 2, n = 6. Check: P+(6) = 3 >= sqrt(6) ~ 2.45. Yes. Let me verify with N = 100, answer should be 100 - (100 - 29) = 29. We use a prime sieve up to $\sqrt{N} = 10^5$ to get small primes. We then iterate over primes $\sqrt{N} < p \le N/2$, we need to compute $\sum (\lfloor N/p \rfloor - 1)$. Group by values of $\lfloor N/p \rfloor$ and use the Lucy_Hedgehog method (or segmented sieve) for prime counting. Finally, use the Meissel-Lehmer method to compute $\pi(N)$ and related prime counting sums.

Pseudocode

Use a prime sieve up to $\sqrt{N} = 10^5$ to get small primes
For primes $p \le \sqrt{N}$, sum $(p - 2)$
For primes $\sqrt{N} < p \le N/2$, we need to compute $\sum (\lfloor N/p \rfloor - 1)$. Group by values of $\lfloor N/p \rfloor$ and use the Lucy_Hedgehog method (or segmented sieve) for prime counting
Use the Meissel-Lehmer method to compute $\pi(N)$ and related prime counting sums

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

• Time: $O(N^{2/3})$ using the Meissel-Lehmer approach
• Space: $O(N^{1/2})$

Answer

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

/*
 * Problem 668: Square Root Smooth Numbers
 *
 * n is square root smooth if all prime factors of n are STRICTLY less than sqrt(n).
 * Count f(N) = |{n <= N : n is square root smooth}|.
 *
 * n > 1 is NOT smooth iff P+(n) >= sqrt(n), i.e., P+(n)^2 >= n.
 *
 * Non-smooth numbers:
 * (A) Primes: pi(N) numbers
 * (B) n = p^2 where p prime, p^2 <= N: pi(sqrtN) numbers (P+(p^2)=p=sqrt(n))
 * (C) n = p*m, p = P+(n), 2 <= m <= p-1, m*p <= N, all prime factors of m < p
 *     (automatic since m < p). For each prime p: min(p-1, N/p) - 1 valid m values.
 *
 * f(N) = 1 + N - pi(N) - pi(sqrtN) - sum_{p prime, p<=N/2} max(0, min(p-1, N/p) - 1)
 */

typedef long long ll;

int main(){
    ll N = 10000000000LL;
    ll sqrtN = 100000LL;

    int sN = (int)sqrtN;
    vector<bool> is_prime(sN + 1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; (ll)i * i <= sN; i++){
        if(is_prime[i]){
            for(int j = i*i; j <= sN; j += i)
                is_prime[j] = false;
        }
    }

    // Lucy_Hedgehog prime counting
    vector<ll> small(sN + 2, 0), large(sN + 2, 0);
    for(int v = 0; v <= sN; v++) small[v] = max(0, v - 1);
    for(int k = 1; k <= sN; k++) large[k] = N / k - 1;

    for(int p = 2; p <= sN; p++){
        if(!is_prime[p]) continue;
        ll pp = (ll)p * p;
        ll pcnt = small[p - 1];

        for(int k = 1; k <= sN && (ll)k * pp <= N; k++){
            ll val = N / ((ll)k * p);
            ll sub;
            if(val <= sN)
                sub = small[(int)val];
            else
                sub = large[(int)((ll)k * p)];
            large[k] -= sub - pcnt;
        }

        for(int v = sN; v >= pp; v--){
            small[v] -= small[v / p] - pcnt;
        }
    }

    auto getPi = [&](ll x) -> ll {
        if(x <= 0) return 0;
        if(x <= sN) return small[(int)x];
        return large[(int)(N / x)];
    };

    ll piN = large[1];
    ll piSqrtN = small[sN]; // pi(sqrtN)

    // Part 1: primes p <= sqrtN, contribution = p - 2 (for p >= 3)
    ll sum1 = 0;
    for(int p = 3; p <= sN; p++){
        if(is_prime[p]) sum1 += p - 2;
    }

    // Part 2: primes sqrtN < p <= N/2, contribution = N//p - 1
    ll maxq = N / (sqrtN + 1);
    ll sum2 = 0;
    for(ll q = 2; q <= maxq; q++){
        ll phi = N / q;
        ll plo = N / (q + 1);
        if(phi <= sqrtN) continue;
        if(plo < sqrtN) plo = sqrtN;
        ll cnt = getPi(phi) - getPi(plo);
        if(cnt > 0)
            sum2 += (q - 1) * cnt;
    }

    ll answer = 1 + N - piN - piSqrtN - sum1 - sum2;
    cout << answer << endl;

    return 0;
}

"""
Problem 668: Square Root Smooth Numbers

A positive integer n is square root smooth if all prime factors < sqrt(n).
Count such n <= N = 10^10 (including 1).

n is NOT square root smooth iff it has a prime factor p >= sqrt(n).
We count the complement.

For each n > 1, let p = P+(n) be largest prime factor.
n is not smooth iff p^2 >= n.

Write n = p * m where m = n/p. Then m < p (from p^2 >= n = pm => p > m,
actually p >= m, and if p = m then n = p^2, P+(n) = p = sqrt(n), not strictly less).

Case A: m = 1, i.e., n = p is prime. Count = pi(N).
Case B: m >= 2, m < p, all prime factors of m < p (auto since m < p).
  For each prime p: m from 2 to min(p-1, N//p).
  Number of valid m = min(p-1, N//p) - 1.

Answer = 1 + N - pi(N) - sum over primes p of (min(p-1, N//p) - 1)
where the sum is over primes 2 <= p <= N//2.

But wait: for p = 2, min(p-1, N//p) - 1 = min(1, 5*10^9) - 1 = 0.
That's correct since m must be >= 2 and < 2, impossible.

For p = 3: min(2, N//3) - 1 = 1. So m = 2, n = 6. Check: P+(6) = 3 >= sqrt(6) ~ 2.45. Yes.

Let me verify with N = 100, answer should be 100 - (100 - 29) = 29.
"""

def solve_small(N):
    """Brute force for verification."""
    count = 0
    for n in range(1, N + 1):
        if n == 1:
            count += 1
            continue
        # Find largest prime factor
        temp = n
        lpf = 0
        d = 2
        while d * d <= temp:
            while temp % d == 0:
                lpf = max(lpf, d)
                temp //= d
            d += 1
        if temp > 1:
            lpf = max(lpf, temp)
        if lpf * lpf < n:  # strictly less: lpf < sqrt(n)
            count += 1
    return count

# Verify: f(100) should be 29
print("f(100) =", solve_small(100))

def solve(N):
    import math
    sqrtN = int(math.isqrt(N))

    # Sieve primes up to sqrtN
    sN = sqrtN
    is_prime = [False, False] + [True] * (sN - 1)
    for i in range(2, int(math.isqrt(sN)) + 1):
        if is_prime[i]:
            for j in range(i*i, sN + 1, i):
                is_prime[j] = False

    # Lucy_Hedgehog prime counting
    small = list(range(-1, sN + 1))  # small[v] = v - 1 for v = 0..sN
    small[0] = 0
    large = [0] * (sN + 2)
    for k in range(1, sN + 1):
        large[k] = N // k - 1

    for p in range(2, sN + 1):
        if not is_prime[p]:
            continue
        pp = p * p
        pcnt = small[p - 1]

        # Update large
        for k in range(1, sN + 1):
            if k * pp > N:
                break
            val = N // (k * p)
            if val <= sN:
                sub = small[val]
            else:
                sub = large[k * p]
            large[k] -= sub - pcnt

        # Update small (from sN down to pp)
        for v in range(sN, pp - 1, -1):
            small[v] -= small[v // p] - pcnt

    def getPi(x):
        if x <= 0:
            return 0
        if x <= sN:
            return small[x]
        return large[N // x]

    piN = large[1]

    # Count non-smooth composites
    # For each prime p with 2 <= p <= N//2:
    #   contribution = min(p-1, N//p) - 1 (if >= 1, else 0)

    # Split: p <= sqrtN and p > sqrtN
    total_non_smooth_composite = 0

    # Part 1: primes p <= sqrtN
    # min(p-1, N//p) = p - 1 since N//p >= sqrtN >= p for p <= sqrtN
    # contribution = p - 2
    for p in range(2, sN + 1):
        if is_prime[p]:
            total_non_smooth_composite += p - 2

    # Part 2: primes sqrtN < p <= N//2
    # min(p-1, N//p) = N//p since N//p < sqrtN < p
    # contribution = N//p - 1
    # Group by q = N//p: primes in (N//(q+1), N//q], contribution = q - 1 each
    maxq = N // (sqrtN + 1)
    for q in range(2, maxq + 1):
        phi = N // q
        plo = N // (q + 1)
        if phi <= sqrtN:
            continue
        if plo < sqrtN:
            plo = sqrtN
        cnt = getPi(phi) - getPi(plo)
        if cnt > 0:
            total_non_smooth_composite += (q - 1) * cnt

    answer = 1 + N - piN - total_non_smooth_composite
    return answer

# Verify small case
print("f(100) via formula =", solve(100))

# Solve the actual problem
print(solve(10**10))