Prime Sieve
(math/prime_sieve.hpp)

View this file on GitHub
Last update: 2026-06-20 09:18:49+09:00
Include: #include "math/prime_sieve.hpp"

Overview

PrimeSieve builds a linear sieve and stores the smallest prime factor of every integer up to a chosen limit. It is intended for contests with many primality, factorization, divisor, totient, or Mobius queries in a bounded range.

For example, after constructing PrimeSieve(1000000), primality checks for any integer through one million take constant time, and factorizations repeatedly divide by a stored smallest prime factor.

What the Sieve Stores

For each integer x >= 2, min_prime_factor(x) is the smallest prime dividing x.

`x`	Smallest prime factor
`2`	`2`
`15`	`3`
`49`	`7`
`91`	`7`

A number x >= 2 is prime exactly when its smallest prime factor is itself.

To factor 360, repeatedly divide by the smallest stored factor:

/ 2 = 180
/ 2 = 90
/ 2 = 45
/ 3 = 15
/ 3 = 5
/ 5 = 1

Therefore $360 = 2^3 \cdot 3^2 \cdot 5$.

Construction

explicit PrimeSieve(int limit = 0);

Construction takes $O(\text{limit})$ time and $O(\text{limit})$ memory.

The implementation is a linear sieve: each composite number is generated from its smallest prime factor only once. This gives linear construction time, unlike the more familiar Eratosthenes analysis of $O(n \log \log n)$.

Euler’s Totient Function

totient(x) returns Euler’s totient function $\varphi(x)$: the number of integers from 1 through x that are coprime to x.

For example, 1, 5, 7, and 11 are the four integers coprime to 12, so totient(12) is 4.

From the distinct prime divisors of x, it is computed as

\[\varphi(x) = x \prod_{p \mid x}\frac{p-1}{p}.\]

Totients are useful for counting reduced fractions and for modular arithmetic, especially Euler’s theorem. See prime_factorization.hpp for a longer explanation and examples.

Mobius Function

mobius(x) returns:

1 for x = 1;
0 when some prime square divides x;
1 or -1 otherwise, depending on whether x has an even or odd number of distinct prime factors.

For example:

mobius(6) = 1 because $6 = 2 \cdot 3$ has two distinct prime factors;
mobius(30) = -1 because $30 = 2 \cdot 3 \cdot 5$ has three;
mobius(12) = 0 because $2^2$ divides 12.

The Mobius function is mainly used for inclusion-exclusion over divisors and for counting objects whose gcd is exactly 1. See prime_factorization.hpp for the Mobius inversion formula.

API

struct PrimeSieve {
    explicit PrimeSieve(int limit = 0);

    int limit() const;
    const std::vector<int>& primes() const;
    const std::vector<int>& min_prime_factors() const;

    bool is_prime(int value) const;
    int min_prime_factor(int value) const;
    std::vector<std::pair<int, int>> factorize(int value) const;
    std::vector<int> divisors(int value) const;
    int totient(int value) const;
    int mobius(int value) const;

    std::vector<int> totient_table() const;
    std::vector<int> mobius_table() const;
};

The limit, query arguments, primes, exponents, totients, and Mobius values all use int. is_prime returns bool. The two stored-table accessors return const std::vector<int>&; the reference remains valid while the sieve object exists. Other vector-valued methods return new vectors by value.

Method	Description	Complexity
`limit()`	Returns the sieve limit.	$O(1)$
`primes()`	Returns all primes up to the limit.	$O(1)$
`min_prime_factors()`	Returns the complete smallest-prime-factor table.	$O(1)$
`is_prime(x)`	Tests whether `x` is prime.	$O(1)$
`min_prime_factor(x)`	Returns the smallest prime divisor of `x`.	$O(1)$
`factorize(x)`	Returns `(prime, exponent)` pairs in increasing order.	$O(\log x)$
`divisors(x)`	Returns all positive divisors in increasing order.	$O(d(x) \log d(x))$
`totient(x)`	Returns Euler’s totient function.	$O(\log x)$
`mobius(x)`	Returns the Mobius function.	$O(\log x)$
`totient_table()`	Returns totients for the whole sieve range.	$O(\text{limit})$
`mobius_table()`	Returns Mobius values for the whole sieve range.	$O(\text{limit})$

Queries require their argument to be within the constructed range.

factorize(1) returns an empty list, while divisors(1) returns a list containing only 1.

The table methods are useful when nearly every value in the range will be queried. Calling totient(x) or mobius(x) separately is usually preferable for only a few values.

When to Use This Instead of Pollard-Rho

Use PrimeSieve when:

there are many queries;
every input is at most a known, manageable limit;
$O(\text{limit})$ memory is acceptable.

Use prime_factorization.hpp when inputs may be large 64-bit values. It avoids the large table, but each factorization is more expensive.

Example

#include "math/prime_sieve.hpp"

#include <iostream>

int main() {
    m1une::math::PrimeSieve sieve(1000000);
    for (const auto& factor : sieve.factorize(360)) {
        std::cout << factor.first << " " << factor.second << "\n";
    }

    std::cout << sieve.totient(12) << "\n";  // 4
    std::cout << sieve.mobius(30) << "\n";   // -1
}

Required by

Math All (math/all.hpp)

Verified with

Code

#ifndef M1UNE_MATH_PRIME_SIEVE_HPP
#define M1UNE_MATH_PRIME_SIEVE_HPP 1

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace math {

struct PrimeSieve {
   private:
    int _limit;
    std::vector<int> _min_prime_factor;
    std::vector<int> _primes;

   public:
    explicit PrimeSieve(int limit = 0) : _limit(0) {
        assert(limit >= 0);
        _limit = limit;
        _min_prime_factor.assign(limit + 1, 0);
        if (limit >= 1) _min_prime_factor[1] = 1;
        for (int value = 2; value <= limit; value++) {
            if (_min_prime_factor[value] == 0) {
                _min_prime_factor[value] = value;
                _primes.push_back(value);
            }
            for (int prime : _primes) {
                if (prime > _min_prime_factor[value] || value > limit / prime) break;
                _min_prime_factor[value * prime] = prime;
            }
        }
    }

    int limit() const {
        return _limit;
    }

    const std::vector<int>& primes() const {
        return _primes;
    }

    const std::vector<int>& min_prime_factors() const {
        return _min_prime_factor;
    }

    bool is_prime(int value) const {
        assert(0 <= value && value <= _limit);
        return value >= 2 && _min_prime_factor[value] == value;
    }

    int min_prime_factor(int value) const {
        assert(2 <= value && value <= _limit);
        return _min_prime_factor[value];
    }

    std::vector<std::pair<int, int>> factorize(int value) const {
        assert(1 <= value && value <= _limit);
        std::vector<std::pair<int, int>> result;
        while (value > 1) {
            const int prime = _min_prime_factor[value];
            int exponent = 0;
            do {
                value /= prime;
                exponent++;
            } while (value > 1 && _min_prime_factor[value] == prime);
            result.emplace_back(prime, exponent);
        }
        return result;
    }

    std::vector<int> divisors(int value) const {
        std::vector<int> result = {1};
        for (const auto& factor : factorize(value)) {
            const int current_size = int(result.size());
            int power = 1;
            for (int exponent = 1; exponent <= factor.second; exponent++) {
                power *= factor.first;
                for (int i = 0; i < current_size; i++) {
                    result.push_back(result[i] * power);
                }
            }
        }
        std::sort(result.begin(), result.end());
        return result;
    }

    int totient(int value) const {
        assert(1 <= value && value <= _limit);
        int result = value;
        for (const auto& factor : factorize(value)) {
            result = result / factor.first * (factor.first - 1);
        }
        return result;
    }

    int mobius(int value) const {
        assert(1 <= value && value <= _limit);
        int result = 1;
        for (const auto& factor : factorize(value)) {
            if (factor.second >= 2) return 0;
            result = -result;
        }
        return result;
    }

    std::vector<int> totient_table() const {
        std::vector<int> result(_limit + 1);
        if (_limit >= 1) result[1] = 1;
        for (int value = 2; value <= _limit; value++) {
            const int prime = _min_prime_factor[value];
            const int reduced = value / prime;
            result[value] = reduced % prime == 0 ? result[reduced] * prime : result[reduced] * (prime - 1);
        }
        return result;
    }

    std::vector<int> mobius_table() const {
        std::vector<int> result(_limit + 1);
        if (_limit >= 1) result[1] = 1;
        for (int value = 2; value <= _limit; value++) {
            const int prime = _min_prime_factor[value];
            const int reduced = value / prime;
            result[value] = reduced % prime == 0 ? 0 : -result[reduced];
        }
        return result;
    }
};

}  // namespace math
}  // namespace m1une

#endif  // M1UNE_MATH_PRIME_SIEVE_HPP

#line 1 "math/prime_sieve.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace math {

struct PrimeSieve {
   private:
    int _limit;
    std::vector<int> _min_prime_factor;
    std::vector<int> _primes;

   public:
    explicit PrimeSieve(int limit = 0) : _limit(0) {
        assert(limit >= 0);
        _limit = limit;
        _min_prime_factor.assign(limit + 1, 0);
        if (limit >= 1) _min_prime_factor[1] = 1;
        for (int value = 2; value <= limit; value++) {
            if (_min_prime_factor[value] == 0) {
                _min_prime_factor[value] = value;
                _primes.push_back(value);
            }
            for (int prime : _primes) {
                if (prime > _min_prime_factor[value] || value > limit / prime) break;
                _min_prime_factor[value * prime] = prime;
            }
        }
    }

    int limit() const {
        return _limit;
    }

    const std::vector<int>& primes() const {
        return _primes;
    }

    const std::vector<int>& min_prime_factors() const {
        return _min_prime_factor;
    }

    bool is_prime(int value) const {
        assert(0 <= value && value <= _limit);
        return value >= 2 && _min_prime_factor[value] == value;
    }

    int min_prime_factor(int value) const {
        assert(2 <= value && value <= _limit);
        return _min_prime_factor[value];
    }

    std::vector<std::pair<int, int>> factorize(int value) const {
        assert(1 <= value && value <= _limit);
        std::vector<std::pair<int, int>> result;
        while (value > 1) {
            const int prime = _min_prime_factor[value];
            int exponent = 0;
            do {
                value /= prime;
                exponent++;
            } while (value > 1 && _min_prime_factor[value] == prime);
            result.emplace_back(prime, exponent);
        }
        return result;
    }

    std::vector<int> divisors(int value) const {
        std::vector<int> result = {1};
        for (const auto& factor : factorize(value)) {
            const int current_size = int(result.size());
            int power = 1;
            for (int exponent = 1; exponent <= factor.second; exponent++) {
                power *= factor.first;
                for (int i = 0; i < current_size; i++) {
                    result.push_back(result[i] * power);
                }
            }
        }
        std::sort(result.begin(), result.end());
        return result;
    }

    int totient(int value) const {
        assert(1 <= value && value <= _limit);
        int result = value;
        for (const auto& factor : factorize(value)) {
            result = result / factor.first * (factor.first - 1);
        }
        return result;
    }

    int mobius(int value) const {
        assert(1 <= value && value <= _limit);
        int result = 1;
        for (const auto& factor : factorize(value)) {
            if (factor.second >= 2) return 0;
            result = -result;
        }
        return result;
    }

    std::vector<int> totient_table() const {
        std::vector<int> result(_limit + 1);
        if (_limit >= 1) result[1] = 1;
        for (int value = 2; value <= _limit; value++) {
            const int prime = _min_prime_factor[value];
            const int reduced = value / prime;
            result[value] = reduced % prime == 0 ? result[reduced] * prime : result[reduced] * (prime - 1);
        }
        return result;
    }

    std::vector<int> mobius_table() const {
        std::vector<int> result(_limit + 1);
        if (_limit >= 1) result[1] = 1;
        for (int value = 2; value <= _limit; value++) {
            const int prime = _min_prime_factor[value];
            const int reduced = value / prime;
            result[value] = reduced % prime == 0 ? 0 : -result[reduced];
        }
        return result;
    }
};

}  // namespace math
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Prime Sieve
(math/prime_sieve.hpp)

Overview

What the Sieve Stores

Construction

Euler’s Totient Function

Mobius Function

API

When to Use This Instead of Pollard-Rho

Example

Required by

Verified with

Code

Prime Sieve (math/prime_sieve.hpp)

Overview

What the Sieve Stores

Construction

Euler’s Totient Function

Mobius Function

API

When to Use This Instead of Pollard-Rho

Example

Required by

Verified with

Code

Prime Sieve
(math/prime_sieve.hpp)