Prime Numbers

  1. Prime and composite numbers are defined for all natural numbers greater than 1 (all numbers less than or equal to 1 are not prime).

  2. All integers less than or equal to 1 are neither prime nor composite.

  3. Prime Number Test – Trial Division:

    ( d | n ) means that ( d ) can divide ( n ) (the symbol | represents divisibility).

    The divisors of a composite number always appear in pairs. If ( d|n ), then ( (n/d)|n ). Therefore, to determine whether a number is prime, we only need to check whether the smaller number can divide ( n ), i.e., we only need to enumerate ( d \leq (n / d) ), which is ( d \times d \leq n ), or ( d \leq \sqrt{n} ).

    The sqrt(n) function is relatively slow to execute.

    ( i * i <= n ) is prone to overflow.

    1bool is_prime(int x)
2{
3    if (x < 2) return false;
4    for (int i = 2; i <= x / i; i++) // x / i is the fastest and least prone to overflow
5    {
6        if (x % i == 0) return false;
7    }
8    return true;
9}

  4. Prime Factorization – Trial Division (Fundamental Theorem of Arithmetic):

    Fundamental Theorem of Arithmetic: Any natural number ( n ) greater than 1, if ( n ) is not prime, can be uniquely decomposed into a product of finite prime numbers: ( n = P_1^{a1} P_2^{a2} P_3^{a3} \dots P_n^{an} ), where ( P_1 < P_2 < P_3 < \dots < P_n ) are prime numbers, and the exponents ( a_i ) are positive integers.

    Note: Prime factorization and prime factors are different. Prime factorization is a process, while prime factors are numbers.

    A composite number decomposed into prime factors contains at most one prime factor greater than ( \sqrt{n} ). (Proof by contradiction: if ( n ) can be decomposed into two prime factors greater than ( \sqrt{n} ), the product of these two prime factors would be greater than ( n ), which contradicts the fact.)

    When enumerating a number ( i ), the factors of ( n ) no longer contain numbers from ( [2, i-1] ) (they have been divided out). If ( n | i ), the factors of ( i ) also no longer contain numbers from ( [2, i-1] ). Therefore, each enumerated number is a prime number.

    A prime factor (or prime divisor) in number theory is a prime number that divides a given positive integer. According to the Fundamental Theorem of Arithmetic, each positive integer can be uniquely represented as a product of its prime factors, regardless of the order of the factors.

    Two positive integers without common prime factors are called coprime. Since 1 has no prime factors, 1 is coprime with any positive integer (including itself).

    A positive integer with only one prime factor is a prime number.

     1void divide(int x)
 2{
 3    for (int i = 2; i <= x / i; i++)
 4    {
 5        if (x % i == 0)
 6        {
 7            int s = 0;
 8            while (x % i == 0) x /= i, s++;
 9            cout << i << ' ' << s << endl;
10        }
11    }
12    if (x > 1) cout << x << ' ' << 1 << endl; // Numbers greater than sqrt(n)
13    cout << endl;
14}

  5. Sieve of Prime Numbers (Naive Sieve):

    Steps: Mark all multiples of numbers in the range ( [2, n-1] ), and the unmarked numbers are prime numbers.

    Principle: Assume there is a number ( p ) not marked by any number in ( [2, p-1] ), which means no number in ( [2, p-1] ) is a multiple of ( p ). Therefore, ( p ) has no divisors in ( [2, p-1] ), so ( p ) is a prime number.

    Harmonic Series: When ( n ) approaches infinity, ( \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \dots + \frac{1}{n} = \ln n + c ) (where ( c ) is Euler’s constant, approximately 0.577).

    Time Complexity: Approximately ( O(n \log n) ) (Note: Here, ( \log ) specifically refers to base 2).

     1int primes[N], cnt; // primes[] stores all prime numbers
 2bool st[N];         // st[x] stores whether x has been sieved
 3
 4void get_primes(int n)
 5{
 6    for (int i = 2; i <= n; i++)
 7    {
 8        if (!st[i]) primes[cnt++] = i;
 9        for (int j = i + i; j <= n; j += i) st[j] = true; // Sieve multiples of i
10    }
11}

  6. Sieve of Eratosthenes (Optimized Sieve):

    Prime Number Theorem: There are ( n / \ln n ) prime numbers in the range ( 1 \sim n ).

    Steps: In the naive sieve, only use prime numbers to sieve. The principle is simple: all composite numbers can be represented as a product of prime factors, so we only need to sieve multiples of prime numbers, and composite numbers will naturally be sieved.

    Time Complexity: ( O(n \log(\log n)) ).

     1int primes[N], cnt; // primes[] stores all prime numbers
 2bool st[N];         // st[x] stores whether x has been sieved
 3
 4void get_primes(int n)
 5{
 6    for (int i = 2; i <= n; i++)
 7    {
 8        if (!st[i]) // If not sieved, it is a prime number. Sieve multiples of prime numbers, ignoring multiples of composite numbers
 9        {
10            primes[cnt++] = i;
11            for (int j = i + i; j <= n; j += i) st[j] = true;
12        }
13    }
14}

  7. Linear Sieve:

    If ( n \approx 10^6 ), the linear sieve and the Sieve of Eratosthenes have similar time efficiency. If ( n \approx 10^7 ), the linear sieve is about twice as fast as the Sieve of Eratosthenes.

    The Sieve of Eratosthenes, although it uses the fact that multiples of prime numbers are not prime to construct the sieve, still has redundant calculations. For example, 30 is not a prime number. When ( i = 2 ), ( 2 * 15 ) is sieved once, and when ( i = 5 ), ( 5 * 6 ) is sieved again, resulting in wasted efficiency.

    When enumerating multiples, we only need to ensure that the current prime number does not divide this multiple. Of course, we need to sieve once before, i.e., ( p ) is the ( p ) of ( m ), so under optimal conditions, for each prime number, all its corresponding multiples are enumerated, ensuring feasibility.

    Core Idea: All composite numbers can be represented as a product of two or more prime numbers.

    Core: Each composite number ( p ) in the range ( 1 \sim n ) is sieved only by its smallest prime factor. (Fundamental Theorem of Arithmetic)

    Principle: Any composite number in the range ( 1 \sim n ) will be sieved, and when sieving, only the smallest prime factor is used. Since each number has only one smallest prime factor, each number is sieved only once, making the linear sieve linear.

    The enumeration stops when the smallest prime factor of ( i ) is reached, i.e., if (i % primes[j] == 0) break;.

    When i % primes[j] != 0, primes[j] must be smaller than the smallest prime factor of ( i ), and primes[j] must be the smallest prime factor of primes[j] * i.

    When i % primes[j] == 0, primes[j] must be the smallest prime factor of ( i ), and primes[j] is also the smallest prime factor of primes[j], so primes[j] is the smallest prime factor of primes[j] * i.

    The key is the break. Without break, the enumeration continues, and the prime numbers encountered later will not be the smallest prime numbers because they are larger than the current prime number, thus achieving optimization.

    ( a \times prime[x] \leq n )

    Property: Any composite number ( n ) must contain a prime factor not exceeding ( \sqrt{n} ). (To be proven)

     1int primes[N], cnt; // primes[] stores all prime numbers
 2bool st[N];         // st[x] stores whether x has been sieved
 3
 4void get_primes(int n)
 5{
 6    for (int i = 2; i <= n; i++)
 7    {
 8        if (!st[i]) primes[cnt++] = i;
 9        // j < cnt is unnecessary because primes[cnt - 1] = current largest prime number
10        // If i is not a prime number, it will break in the middle
11        // If i is a prime number, then primes[cnt - 1] = i, also ensuring j < cnt
12        for (int j = 0; primes[j] <= n / i; j++)
13        {
14            st[primes[j] * i] = true;
15            if (i % primes[j] == 0) break;
16            // If i is a multiple of a previous prime number, it means that i will be sieved by a larger number multiplied by this small prime number
17            // Similarly, subsequent prime numbers are unnecessary, so we can break the loop
18        }
19    }
20}

Perfect Squares

  1. An integer ( a ) is a perfect square if it is the square of some integer, i.e., there exists an integer ( b ) such that ( a = b^2 ).

  2. If a positive integer is a perfect square, its prime factors must all have even exponents.

    For example, ( 36 = 2^2 \times 3^2 ), ( 900 = 2^2 \times 3^2 \times 5^2 ).

  3. A non-perfect square has at least one prime factor with an odd exponent.

    For example, ( 18 = 2^1 \times 3^2 ).

    To turn ( 18 ) into a perfect square, we need to make the odd exponent even. Here, we can multiply by 2 to turn ( 2^1 ) into ( 2^2 ), resulting in ( 18 \times 2 = 36 ), which is a perfect square.

     1// Given a positive integer n, find the smallest positive integer x such that their product is a perfect square.
 2// First, we sieve out all prime factors with even exponents, and the remaining ones are either prime factors with odd exponents or 1, which is our result.
 3#include <iostream>
 4
 5using namespace std;
 6
 7typedef long long LL;
 8
 9int main()
10{
11    LL n;
12    scanf("%lld", &n);
13    for (LL i = 2; i <= n / i; i++)
14        while (n % (i * i) == 0) n /= i * i;
15    printf("%lld", n);
16
17    return 0;
18}

Permutation Problem of Multisets

Permutation formula:

$$ \frac{(\alpha_1 + \alpha_2 + \dots + \alpha_k)!}{\alpha_1! \cdot \alpha_2! \cdot \dots \cdot \alpha_k!} $$

Divisors

Fundamental Theorem of Arithmetic: Any natural number ( n ) greater than 1, if ( n ) is not prime, can be uniquely decomposed into a product of finite prime numbers: ( n = P_1^{\alpha_1} P_2^{\alpha_2} P_3^{\alpha_3} \dots P_n^{\alpha_n} ), where ( P_1 < P_2 < P_3 < \dots < P_n ) are prime numbers, and the exponents ( \alpha_i ) are positive integers.

Example:

  1. ( 12 ) (divisors: 1, 2, 3, 4, 6, 12)
  2. ( 12 = 2^2 \times 3^1 )

Number of Divisors

( \text{cnt} = (\alpha_1 + 1) \times (\alpha_2 + 1) \dots (\alpha_k + 1) )

Example:

( \text{cnt} = (2 + 1) \times (1 + 1) = 3 \times 2 = 6 )

Sum of Divisors

( \text{sum} = (P_1^0 + P_1^1 + P_1^2 + \dots + P_1^{\alpha_1}) \times (P_2^0 + P_2^1 + P_2^2 + \dots + P_2^{\alpha_2}) \times \dots \times (P_k^0 + P_k^1 + P_k^2 + \dots + P_k^{\alpha_k}) )

Example:

( \text{sum} = (1 + 2^1 + 2^2) \times (1 + 3^1) = 7 \times 4 = 28 )

This is essentially combinatorial. For 2, we can take it 0, 1, or 2 times, and for 3, we can take it 0 or 1 time.

$$ \text{Problem: Given a number } 1 \leq \text{sum} \leq 2 \times 10^9, \text{ find all numbers whose sum of divisors equals sum.} $$

Analysis:

The problem is to find a number whose sum of divisors equals sum.

  1. First, we can roughly estimate how many terms of the form ( (P_1^0 + P_1^1 + P_1^2 + \dots + P_1^{\alpha_1}) ) there are.

    ( (1 + 2) \times (1 + 3) \times (1 + 5) \times (1 + 7) \times (1 + 11) \times (1 + 13) \times (1 + 17) \times (1 + 19) \times (1 + 21) \times (1 + 23) )

    ( = 3 \times 4 \times 6 \times 8 \times 12 \times 14 \times 18 \times 20 \times 22 \times 24 )

    ( = 18 \times 10^9 )

    ( > 2 \times 10^9 )

    So there are likely no more than 10 terms. This problem can be solved using DFS to search for each ( P_i ) and ( \alpha_i ), with a recursion depth of no more than 10 layers. However, pruning is necessary; otherwise, each layer starts enumerating from 2, resulting in high time complexity.

  2. sum generally has two cases:

    1. ( \text{sum} = (1 + P_1)(1 + P_2 + \dots) \dots )

      If ( P_1 \geq \sqrt{\text{sum}} ), then ( (1 + P_1)(1 + P_2) > (1 + P_1)^2 > P_1^2 \geq \text{sum} ).

      Therefore, ( P_1 \leq \sqrt{\text{sum}} ).

    2. ( \text{sum} = (1 + P_1 + P_1^2 + \dots)(1 + \dots) > P_1^2 ).

      If ( P_1 \geq \sqrt{\text{sum}} ), then ( 1 + P_1 + P_1^2 > P_1^2 \geq \text{sum} ).

      Therefore, ( P_1 \leq \sqrt{\text{sum}} ).

    Special Case: If ( P_1 \geq \sqrt{\text{sum}} ), then ( \text{sum} = 1 + P_1 ).

    If there exist ( P_i \geq \sqrt{\text{sum}} ) and ( P_j \geq \sqrt{\text{sum}} ), and ( P_i < P_j ), then according to the above conclusion, ( \text{sum} = 1 + P_i ) and ( \text{sum} = 1 + P_j ), which implies ( P_i = P_j ), contradicting the condition.

    Therefore, if there is a ( P_1 \geq \sqrt{\text{sum}} ) satisfying ( s = 1 + P_1 ), then there is only one such ( P_1 ).

    When ( \alpha_1 = 1 ) and ( \text{sum} = 1 + P_1 ), we only need to check whether ( \text{sum} - 1 ) is a prime number.

    For example, ( s = 12 ), ( s - 1 = 11 ). If ( s - 1 ) is a prime number, then there are only 1 and itself, and their sum must equal ( s ). Conversely, if ( s - 1 ) is a prime number, then there are only 1 and ( s - 1 ) as divisors, and their sum must equal ( s ).

    Essentially, for each layer of sum, we search for ( P_1 ) and divide sum by this term:

    $$ \frac{\text{sum}}{1 + P_1^1 + \dots + P_1^{\alpha_1}} $$

    The entire process is about finding whether there is a ( (1 + P_1 + P_1^2 + \dots + P_1^{\alpha_1}) ) that satisfies:

    $$ \text{sum} % (1 + P_1 + P_1^2 + \dots + P_1^{\alpha_1}) == 0 $$

    If such a term exists, we divide sum by ( (1 + P_1 + P_1^2 + \dots + P_k^{\alpha_1}) ) and proceed to the next layer with DFS.

    1for (primes: 2, 3, 5, 7, ...)
2    for (α: 1, 2, 3, ...)
3        if (sum mod (1 + p1 + p1^2 + ... + p1^α1) == 0)
4            dfs(next layer)

  3. The three parameters of dfs(int last, int prod, int s):

    1. last: The last enumerated prime number, to avoid repetition. For example, after enumerating 2, the next layer should start from 3, not from the beginning.

    2. prod: The product of the highest-degree terms in each parenthesis of ( \text{sum} = (P_1^0 + P_1^1 + \dots + P_1^{\alpha_1}) \times (P_2^0 + P_2^1 + \dots + P_2^{\alpha_2}) \times \dots \times (P_k^0 + P_k^1 + \dots + P_k^{\alpha_k}) ). For example, if ( \text{sum} = (1 + 2 + 2^2) \times (1 + 3 + 3^3) \times (1 + \dots) ), then at the third layer, ( \text{prod} = 2^2 \times 3^3 ).

      By the Fundamental Theorem of Arithmetic, a number ( N = P_1^{\alpha_1} \times P_2^{\alpha_2} \times \dots \times P_k^{\alpha_k} ), and prod stores such a product, which is the answer.

      Example: To determine whether the sum of divisors of a number ( N ) is what we need.

      From ( N = P_1^{\alpha_1} \times P_2^{\alpha_2} \times \dots \times P_k^{\alpha_k} ), we get ( 12 = 2^2 \times 3^1 ).

      From ( \text{sum} = (P_1^0 + P_1^1 + \dots + P_1^{\alpha_1}) \times (P_2^0 + P_2^1 + \dots + P_2^{\alpha_2}) \times \dots \times (P_k^0 + P_k^1 + \dots + P_k^{\alpha_k}) ), we get ( \text{sum} = (1 + 2 + 2^2) \times (1 + 3) ).

      Therefore, we can derive the answer ( N ) from the product of the highest-degree terms in each parenthesis of sum.

    3. s: When ( s == 1 ), it means the last term has been searched, and the answer is saved and returned.

      Special case: If ( P_i \geq \sqrt{s} ), and ( s - 1 = P_i ), then the answer is saved.

      The remaining case is the general case where ( P_i < \sqrt{s} ). Each time a term that can divide sum is found, we recurse to the next layer, updating s to the value after division.

Code

 1#include <iostream>
 2#include <algorithm>
 3
 4using namespace std;
 5
 6const int N = 50000; // N = sqrt(2e9)
 7int primes[N], cnt;
 8bool st[N];
 9int ans[N], len; // Store the answers and the number of answers
10
11void get_primes(int n) // Linear sieve of prime numbers
12{
13    for (int i = 2; i <= n; i++)
14    {
15        if (!st[i]) primes[cnt++] = i;
16        for (int j = 0; i * primes[j] <= n; j++)
17        {
18            st[i * primes[j]] = true;
19            if (i % primes[j] == 0) break;
20        }
21    }
22}
23
24bool is_prime(int n) // Check if a number is prime
25{
26    if (n < N) return !st[n]; // If not sieved, it is a prime number
27    for (int i = 0; primes[i] <= n / primes[i]; i++)
28    {
29        if (n % primes[i] == 0) return false;
30    }
31    return true;
32}
33
34// last: The index of the last prime number enumerated, prod: The partial product of the answer, s: The current sum of divisors to be decomposed
35void dfs(int last, int prod, int s)
36{
37    if (s == 1) // If the decomposition ends with 1, save the answer and return
38    {
39        ans[len++] = prod;
40        return;
41    }
42
43    // First, handle the special case where P1 >= sqrt(s), s - 1 = P1, i.e., check if s - 1 is a prime number. If so, s - 1 is an answer
44    if (s - 1 > (last < 0 ? 1 : primes[last]) && is_prime(s - 1)) // It must be a prime number and greater than the last prime number
45        ans[len++] = prod * (s - 1);
46
47    for (int i = last + 1; primes[i] <= s / primes[i]; i++) // Enumerate from the next prime number
48    {
49        int p = primes[i];
50        for (int j = 1 + p, t = p; j <= s; t *= p, j += t) // j == 1 + Pi^1 + Pi^2 + ... + Pi^αi
51        {
52            if (s % j == 0) dfs(i, prod * t, s / j); // When j is a term of s, recurse to the next layer
53        }
54    }
55}
56
57int main()
58{
59    get_primes(N - 1);
60
61    int n;
62    while (cin >> n)
63    {
64        len = 0;
65        dfs(-1, 1, n);
66
67        // After searching, sort the answers
68        cout << len << endl;
69        if (len)
70        {
71            sort(ans, ans + len);
72            for (int i = 0; i < len; i++) cout << ans[i] << ' ';
73            puts("");
74        }
75    }
76
77    return 0;
78}