Prime Numbers

Definitions of prime and composite numbers can be found in Number Theory Basics.

Prime-counting function: The number of primes less than or equal to \(x\), denoted by \(\pi(x)\). As \(x\) increases, we have the approximation: \(\pi(x) \sim \dfrac{x}{\ln(x)}\).

Primality Testing

Primality testing can be used to determine whether a given natural number is prime.

There are two types of primality tests:

Deterministic tests: Absolutely determine whether a number is prime. Common examples include trial division, the Lucas–Lehmer test, and elliptic curve primality proving.
Probabilistic tests: Usually much faster than deterministic tests, but may (with very low probability) incorrectly identify a composite number as prime (though the reverse does not happen). Therefore, numbers that pass a probabilistic primality test are called probable primes until their primality can be deterministically proven. Composite numbers that pass such tests are called pseudoprimes. There are many specific types of pseudoprimes, the most common being Fermat pseudoprimes, which are composite numbers satisfying Fermat's little theorem. Common examples of probabilistic tests include the Miller–Rabin test.

Trial Division

A brute-force approach is to enumerate each number from small to large and check if it divides the given number.

Reference Implementation

C++Python

bool isPrime(int a) {
  if (a < 2) return false;
  for (int i = 2; i < a; ++i)
    if (a % i == 0) return false;
  return true;
}

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, a):
        if a % i == 0:
            return False
    return True

This approach is very safe, but is it necessary to check every number?

It is easy to observe the following fact: If \(x\) is a divisor of \(a\), then \(\frac{a}{x}\) is also a divisor of \(a\).

This tells us that for each pair \((x, \frac{a}{x} )\), it is sufficient to check only one of them. For convenience, we only examine the smaller number in each pair. It is not hard to see that all these smaller numbers lie in the interval \([1, \sqrt{a}]\).

Since \(1\) is definitely a divisor, we do not check it.

Reference Implementation

C++Python

bool isPrime(int a) {
  if (a < 2) return 0;
  for (int i = 2; (long long)i * i <= a; ++i)  // Prevent overflow
    if (a % i == 0) return 0;
  return 1;
}

def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True

Fermat Primality Test

The Fermat primality test is the simplest probabilistic primality test.

We can derive a primality testing idea from Fermat's little theorem:

The basic idea is to repeatedly select a base \(a\) in \([2, n-1]\) and check whether \(a^{n-1} \equiv 1 \pmod n\) holds each time.

Reference Implementation

C++Python

bool fermat(int n) {
  if (n < 3) return n == 2;
  // test_time is the number of tests; it is recommended to set it to an integer not less than 8
  // to ensure correctness, but not too large to avoid affecting efficiency
  for (int i = 1; i <= test_time; ++i) {
    int a = rand() % (n - 2) + 2;
    if (quickPow(a, n - 1, n) != 1) return false;
  }
  return true;
}

def fermat(n):
    if n < 3:
        return n == 2
    # test_time is the number of tests; it is recommended to set it to an integer not less than 8
    # to ensure correctness, but not too large to avoid affecting efficiency
    for i in range(1, test_time + 1):
        a = random.randint(0, 32767) % (n - 2) + 2
        if quickPow(a, n - 1, n) != 1:
            return False
    return True

If \(a^{n−1} \equiv 1 \pmod n\) but \(n\) is not prime, then \(n\) is called a Fermat pseudoprime to base \(a\). In practice, we observe that if \(a^{n−1} \equiv 1 \pmod n\), then \(n\) is usually prime. However, counterexamples exist: for \(n = 341\) and \(a = 2\), although \(2^{340}\equiv 1 {\pmod {341}}\), \(341 = 11 \cdot 31\) is composite. In fact, for any fixed base \(a\), there are infinitely many such counterexamples¹.

Since the Fermat primality test cannot guarantee correctness for a single base, a natural idea is to check multiple bases. However, even if all bases \(a\) coprime to \(n\) are checked, it still cannot guarantee that \(n\) is prime. That is, the converse of Fermat's little theorem does not hold: even if \(a^{n-1}\equiv 1\pmod n\) for all \(a\perp n\), \(n\) may not be prime. Such numbers are called Carmichael numbers. There are also infinitely many of them. This forces us to seek stricter primality tests.

Miller–Rabin Primality Test

The Miller–Rabin primality test (Miller–Rabin primality test) is a better method for primality determination. It was optimized from the Fermat primality test by Miller and Rabin. Like other probabilistic primality tests, it can only detect pseudoprimes. To ensure primality, a much slower deterministic algorithm is needed. However, in practice, no known numbers pass the Miller–Rabin test and other advanced probabilistic tests but are actually composite, so we can use it with confidence.

Ignoring the complexity of multiplication, the time complexity for \(k\) rounds of testing on a number \(n\) is \(O(k \log n)\). The Miller–Rabin primality test is often used for high-precision numbers, where the time complexity is \(O(k \log^3n)\). Using techniques like FFT, it can be optimized to \(O(k \log^2n \log \log n \log \log \log n)\).

To address the challenge posed by Carmichael numbers, the Miller–Rabin primality test further considers the following property of primes:

Quadratic Residue Theorem

If \(p\) is an odd prime, then the solutions to \(x^2 \equiv 1 \pmod p\) are \(x \equiv 1 \pmod p\) or \(x \equiv p - 1 \pmod p\).

Proof

It is easy to verify that when \(p\) is an odd prime, \(x\equiv 1\pmod p\) and \(x\equiv p-1\pmod p\) both satisfy the equation. By Lagrange's theorem, these are all the solutions.

Combining Fermat's little theorem and the quadratic residue theorem, we obtain the Miller–Rabin primality test:

Factor the exponent \(n−1\) in \(a^{n-1} \equiv 1 \pmod n\) as \(n−1=u \times 2^t\);
In each round of testing, for a randomly chosen \(a\), first compute \(v = a^{u} \bmod n\), then perform at most \(t\) squaring operations on this value;
During the process, if a nontrivial square root of \(1\) (i.e., a root other than \(\pm 1\)) is found, the number can be judged as composite;
Otherwise, use the Fermat primality test for judgment.

There are also some implementation details:

For one round of testing, if at some point \(a^{u \times 2^s} \equiv n-1 \pmod n\), then all subsequent squaring operations will yield \(1\), and the test can be passed directly.
If a nontrivial square root \(a^{u \times 2^s} \not\equiv n-1 \pmod n\) is found, then all subsequent squaring operations will yield \(1\). You can choose to return false directly or after \(t\) squaring operations.

This yields a more correct Miller–Rabin implementation (from fjzzq2002):

Reference Implementation

C++Python

bool millerRabin(int n) {
  if (n < 3 || n % 2 == 0) return n == 2;
  if (n % 3 == 0) return n == 3;
  int u = n - 1, t = 0;
  while (u % 2 == 0) u /= 2, ++t;
  // test_time is the number of tests; it is recommended to set it to an integer not less than 8
  // to ensure correctness, but not too large to avoid affecting efficiency
  for (int i = 0; i < test_time; ++i) {
    // 0, 1, n-1 can pass directly; a ranges in [2, n-2]
    int a = rand() % (n - 3) + 2, v = quickPow(a, u, n);
    if (v == 1) continue;
    int s;
    for (s = 0; s < t; ++s) {
      if (v == n - 1) break;  // Obtain the trivial square root n-1, pass this round of testing
      v = (long long)v * v % n;
    }
    // If a nontrivial square root is found, it will run until s == t because it cannot break early
    // If the Fermat primality test fails, v will never equal -1 before s == t
    if (s == t) return 0;
  }
  return 1;
}

def millerRabin(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    if n % 3 == 0:
        return n == 3
    u, t = n - 1, 0
    while u % 2 == 0:
        u = u // 2
        t = t + 1
    # test_time is the number of tests; it is recommended to set it to an integer not less than 8
    # to ensure correctness, but not too large to avoid affecting efficiency
    for i in range(test_time):
        # 0, 1, n-1 can pass directly; a ranges in [2, n-2]
        a = random.randint(2, n - 2)
        v = pow(a, u, n)
        if v == 1:
            continue
        s = 0
        while s < t:
            if v == n - 1:
                break
            v = v * v % n
            s = s + 1
        # If a nontrivial square root is found, it will run until s == t because it cannot break early
        # If the Fermat primality test fails, v will never equal -1 before s == t
        if s == t:
            return False
    return True

It can be proven² that for an odd composite number \(n > 9\), the probability of passing the Miller–Rabin primality test with a randomly chosen base \(a\) is at most one-fourth. Therefore, after randomly selecting \(k\) bases, the probability of incorrectly judging a composite number as prime is at most \(1/4^k\).

Proof

Let \(n-1=u2^t\), where \(u\) is odd and \(t\) is a positive integer. Then, the integer \(n\) passes the Miller–Rabin primality test with base \(a\) if

\[ a^u\equiv 1{\textstyle\pmod n},\text{ or }a^{u2^i}\equiv -1{\textstyle\pmod n}\text{ for some }0\le i < t. \]

Denote the set of such \(a\) (modulo \(n\)) as \(S\). We need to show that

\[ |S| \le \dfrac14\varphi(n). \]

Here, \(\varphi(n)\) is the Euler totient function. The proof is divided into three steps.

Step 1: Let \(\ell\) be the largest positive integer such that \(2^\ell \mid p-1\) for all prime factors \(p\) of \(n\). Then, it can be shown that

\[ S\subseteq S' = \{a\bmod n:a^{u2^{\ell-1}}\equiv\pm 1{\textstyle\pmod n}\}. \]

Elements \(a\) in set \(S\) have only two possibilities. If \(a^u\equiv 1\pmod n\), then obviously \(a^{u2^{\ell-1}}\equiv 1\pmod n\) also holds, i.e., \(a\in S'\). If \(a^{u2^i}\equiv -1\pmod n\) for some \(0\le i < t\), then for any prime factor \(p\mid n\), we have \(a^{u2^i}\equiv-1\pmod p\). Let \(\delta_p(a)\) be the order of \(a\) modulo \(p\). Then, clearly \(\delta_p(a)\mid u2^{i+1}\) but \(\delta_p(a)\nmid u2^{i}\), which implies that the exponent of \(2\) in the prime factorization of \(\delta_p(a)\) is exactly \(i+1\), so \(2^{i+1}\mid\delta_p(a)\). By Fermat's little theorem, \(\delta_p(a)\mid p-1\), so \(2^{i+1}\mid p-1\). This holds for all prime factors \(p\) of \(n\). Therefore, \(i+1\le\ell\). This implies \(a^{u2^{\ell-1}} = (a^{u2^i})^{2^{\ell-1-i}} \equiv \pm 1 \pmod n\), and again \(a\in S'\). Combining both possibilities, we get \(S\subseteq S'\).

Step 2: Compute the size of \(|S'|\).

Suppose \(n\) has prime factorization \(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\). Then, by the Chinese remainder theorem, the condition \(a^{u2^{\ell - 1}}\equiv 1\pmod n\) is equivalent to \(a^{u2^{\ell - 1}}\equiv 1\pmod{p_i^{e_i}}\) for all \(p_i^{e_i}\). Since primitive roots modulo odd prime powers \(p_i^{e_i}\) always exist, the number of solutions to the congruence \(a^{u2^{\ell - 1}}\equiv 1\pmod{p_i^{e_i}}\) is

\[ \gcd(u2^{\ell-1},p_i^{e_i-1}(p_i-1)) = \gcd(u2^{\ell-1},p_i-1) = 2^{\ell-1}\gcd(u,p_i-1). \]

The first equality holds because \(u\) is a divisor of \(n-1\) and cannot be a multiple of \(p_i\); the second equality holds due to the choice of \(\ell\). Therefore, by the Chinese remainder theorem, the number of solutions to \(a^{u2^{\ell-1}}\equiv 1\pmod n\) is

\[ \prod_{p\mid n}2^{\ell-1}\gcd(u,p-1). \]

Similarly, the condition \(a^{u2^{\ell - 1}}\equiv -1\pmod n\) is equivalent to \(a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}\) for all \(p_i^{e_i}\). For any factor \(p_i^{e_i}\), the condition \(a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}\) is equivalent to \(a^{u2^{\ell - 1}}\not\equiv 1\pmod{p_i^{e_i}}\) and \(a^{u2^{\ell}}\equiv 1\pmod{p_i^{e_i}}\). Similar to above, the number of solutions to \(a^{u2^{\ell}}\equiv 1\pmod{p_i^{e_i}}\) is \(2^{\ell}\gcd(u,p_i-1)\), so the number of solutions to \(a^{u2^{\ell - 1}}\equiv -1\pmod{p_i^{e_i}}\) is also

\[ 2^{\ell}\gcd(u,p_i-1) - 2^{\ell-1}\gcd(u,p_i-1) = 2^{\ell-1}\gcd(u,p_i-1). \]

Applying the Chinese remainder theorem again, the number of solutions to \(a^{u2^{\ell - 1}}\equiv -1\pmod n\) is

\[ \prod_{p\mid n}2^{\ell-1}\gcd(u,p-1). \]

Therefore, combining both cases, we have

\[ |S'| = 2\prod_{p\mid n}2^{\ell-1}\gcd(u,p-1). \]

Step 3: Prove \(|S'|\le\varphi(n)/4\).

Combining with the expression for Euler's totient function \(\varphi(n)=\prod_ip_i^{e_i-1}(p_i-1)\), we have

\[ \dfrac{\varphi(n)}{|S'|} = \dfrac{1}{2}\prod_ip_i^{e_i-1}\dfrac{p_i-1}{2^{\ell-1}\gcd(u,p_i-1)}. \]

For each \(i\), the factor \(p_i^{e_i-1}\dfrac{p_i-1}{2^{\ell-1}\gcd(u,p_i-1)}\) is an even number, so \(\varphi(n)/|S'|\) is an integer. Suppose \(|S'|\le\varphi(n)/4\) does not hold. Then necessarily \(\varphi(n)/|S'|=1,2,3\), i.e.,

\[ \prod_ip_i^{e_i-1}\dfrac{p_i-1}{2^{\ell-1}\gcd(u,p_i-1)} = 2,4,6. \]

Since each factor in the product is even, this product either has only one factor equal to \(2,4,6\), or has exactly two factors both equal to \(2\).

First, consider the case with two factors. In this case, neither factor has an odd prime factor, so \(p_i^{e_i-1}=1\), i.e., \(n\) is square-free. Without loss of generality, let \(n=p_1p_2\) with \(p_1<p_2\) both prime. Both factors equal \(2\), so \(p_i-1=2^{\ell}\gcd(u,p_i-1)\). Therefore, \(p_i=1+2^\ell m_i\), where \(m_i\) is odd and \(m_i\mid u\). Taking \(p_1p_2=n=1+u2^t\) modulo \(m_1\) gives \(p_1p_2\equiv 1\pmod{m_1}\), so \(p_2\equiv 1\pmod{m_1}\), implying \(m_1\mid m_2\). The converse also holds. This means \(m_1=m_2\), i.e., \(p_1=p_2\), contradicting \(p_1<p_2\). This case is impossible.

Finally, consider the case with only one factor, i.e., composite \(n=p^e\) with \(e>1\). Then, necessarily \(p^{e-1}\mid 2,4,6\). Thus, the only possibility is \(p=3,e=2\), i.e., \(n=9\), contradicting the assumption \(n>9\). This case is also impossible.

Combining all cases, we conclude that \(|S'|\le\varphi(n)/4\) holds.

Combining the three steps, we have \(|S|\le |S'|\le \varphi(n)/4\) for all odd composite numbers \(n>9\).

Additionally, assuming the generalized Riemann hypothesis (GRH) holds, testing all integers in \([2, \min\{n-2, \lfloor 2\ln^2 n \rfloor\}]\) is sufficient to deterministically determine the primality of \(n\).³

In the scope of OI, primality testing is usually performed for numbers in the range \([1, 2^{64})\). For numbers in \([1, 2^{32})\), using the three bases \(\{2, 7, 61\}\) for the Miller–Rabin primality test can deterministically determine primality; for numbers in \([1, 2^{64})\), using the seven bases \(\{2, 325, 9375, 28178, 450775, 9780504, 1795265022\}\) for the Miller–Rabin primality test can deterministically determine primality.⁴

Alternatively, one can use \(\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}\) (the first \(12\) primes) to test primes in \([1, 2^{64})\).

Note that when using the numbers \(a\) from the above sequences as bases to test the primality of \(n\):

All numbers must be used, not just those less than \(n\);
Replace \(a\) with \(a \bmod n\);
If \(a \equiv 0 \pmod n\) or \(a \equiv \pm 1 \pmod n\), skip this round of testing.

Anti-prime Numbers

As the name suggests, prime numbers have exactly two factors, so anti-prime numbers are those with the most factors (and the smallest value when the number of factors is the same). Thus, anti-prime numbers are defined relative to a set.

An intuitive definition of anti-prime numbers is: In a set of positive integers, the number with the most factors and the smallest value is the anti-prime number.

Anti-prime Numbers

For a positive integer \(n\), if any positive integer less than \(n\) has fewer divisors than \(n\), then \(n\) is called an anti-prime number (also known as highly composite numbers).

Note

Note the distinction from emirp, which refers to primes that remain prime when their digits are reversed (e.g., 149 and 941 are both emirps, but 101 is not).

Process

So, how do we find anti-prime numbers?

First, since we need the number of factors, the first step is prime factorization. Decompose \(n\) into \(n=p_{1}^{k_{1}}p_{2}^{k_{2}} \cdots p_{n}^{k_{n}}\), where \(p\) are primes and \(k\) are their exponents. Then the total number of factors is \((k_1+1) \times (k_2+1) \times (k_3+1) \cdots \times (k_n+1)\).

However, prime factorization is computationally expensive, and results from previous numbers cannot be reused. So we need a different approach.

Let's observe the characteristics of anti-prime numbers.

Anti-prime numbers are products of powers of consecutive primes starting from \(2\).
The exponent of a smaller prime is greater than or equal to that of a larger prime, i.e., in \(n=p_{1}^{k_{1}}p_{2}^{k_{2}} \cdots p_{n}^{k_{n}}\), we have \(k_1 \geq k_2 \geq k_3 \geq \cdots \geq k_n\).

Explanation:

If not starting from consecutive primes beginning with \(2\), then if the exponents remain unchanged, replacing a prime with a smaller prime keeps the number of factors the same but reduces \(n\). Swapping to consecutive primes starting from \(2\) minimizes \(n\).
If the exponent of a smaller prime is less than that of a larger prime, swapping these two primes (keeping exponents unchanged) keeps the number of factors the same but reduces \(n\).

Additionally, there are two issues:

For a given \(n\), up to which prime should we enumerate?

The extreme case is \(n=p_{1}p_{2} \cdots p_{n}\), so we only need to multiply consecutive primes until the product is just less than or equal to \(n\). If we enumerate larger primes, it implies that some earlier prime's exponent is \(0\), which cannot yield an anti-prime.
Up to what power should we enumerate?

Consider an extreme case: if the smallest prime raised to some power already exceeds the given \(n\) (maximum value), then expanding into other forms, the maximum exponent must be less than this power. In the extreme case where \(n\) is decomposed into powers of \(2\), enumerate up to \(\lfloor\log_2 n\rfloor\).

With these details, how do we implement it concretely?

We can think of each step as traversing a tree where each prime is a root node, and we search layer by layer. When do we stop?

The current number exceeds our target number;
The current factor is no longer needed;
The current factor exceeds our desired factor;
The current factor exactly matches our desired factor (then decide whether to update the minimum \(\mathit{ans}\)).

Then, in dfs, we recursively enumerate exponents layer by layer.

Example Problems

Codeforces 27E. A number with a given number of divisors

Find the smallest natural number with a given number of divisors. The answer is guaranteed not to exceed \(10^{18}\).

Solution Idea

For such problems, we only need to use the number of divisors as the return condition for dfs and continuously update the found minimum value.

Reference Code

#include <iostream>
constexpr int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
// The product of primes in p exceeds 1e18

int n;
long long ans = 2e18;

// u: index of the current prime in p
// num: current constructed number
// cnt: current number of divisors
// pre: exponent of the previous factor, limiting the exponent choice for this step
void dfs(int u, long long num, long long cnt, int pre) {
  if (cnt > n || u >= 15) return;
  if (cnt == n) return ans = std::min(ans, num), void();
  for (int i = 1; i <= pre; ++i) {
    if (num * p[u] > ans) break;  // Pruning
    dfs(u + 1, num *= p[u], cnt * (i + 1), i);
  }
}

int main() {
  std::cin >> n;
  dfs(0, 1, 1, 59);  // floor(log2(1e18))=19
  std::cout << ans << std::endl;
  return 0;
}

ZOJ 2562 More Divisors

Find the number with the most divisors not exceeding \(n\).

Solution Idea

The idea is the same as above, but the dfs return condition needs to be adjusted. Note the data range of such problems; 32-bit integers may overflow.

Reference Code

#include <iostream>

int p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
unsigned long long n;
unsigned long long ans,
    ans_num;  // ans is the largest anti-prime number within n (continuously updated), ans_num is the divisor count of ans.

// depth: current prime index being enumerated
// temp: current number value when divisor count is num
// num: current divisor count
// up: exponent limit of the previous prime, constrains the upper bound of the current prime's exponent
void dfs(int depth, unsigned long long temp, unsigned long long num, int up) {
  if (depth >= 16 || temp > n) return;
  if (num > ans_num) {  // Update answer
    ans = temp;
    ans_num = num;
  }
  if (num == ans_num && ans > temp) ans = temp;  // Update answer
  for (int i = 1; i <= up; i++) {
    if (temp * p[depth] > n)
      break;  // Pruning: if adding this multiplier results in a number larger than n, it cannot be the optimal solution
    dfs(depth + 1, temp *= p[depth], num * (i + 1),
        i);  // Take one of this multiplier, proceed to search for the next multiplier
  }
  return;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n) {
    ans_num = 0;
    dfs(0, 1, 1, 60);
    cout << ans << '\n';
  }
  return 0;
}

References and Notes

Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi, "Complexity Estimates for Fourier-Motzkin Elimination", Journal of Functional Programming 16:2 (2006) pp 197-217.
Number Theory Part 1: Primes and Primality Testing
Miller–Rabin and Pollard–Rho Study Notes - Bill Yang's Blog
Primality test - Wikipedia
Fermat pseudoprime - Wikipedia
Peach's Algorithm Notes - Detailed Explanation of Anti-prime Numbers (acm/OI)
The Rabin-Miller Primality Test
Highly composite number - Wikipedia

Pomerance, Carl, John L. Selfridge, and Samuel S. Wagstaff. "The pseudoprimes to 25⋅ 10⁹." Mathematics of Computation 35, no. 151 (1980): 1003-1026. Theorem 1 shows that for a fixed base \(a\), there are infinitely many composite numbers that can pass the stronger Miller–Rabin primality test. ↩
This conclusion and its proof refer to Section 3.5 of Crandall, Richard, and Carl Pomerance. Prime numbers: a computational perspective. New York, NY: Springer New York, 2005. ↩
Bach, Eric , "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55:191 (1990) pp 355–380. ↩
For more similar results, refer to Deterministic variant of the Miller–Rabin primality test. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用