题解 | #有限域#

题目链接

有限域

题目描述

根据抽象代数中的一个定理，一个大小为 $q$ 的有限域存在，当且仅当 $q$ 是某个素数 $p$ 的方幂，即 $q = p^k$ ，其中 $p$ 是素数， $k$ 是正整数 ( $k \ge 1$ )。

给定一个整数 $n$ ，求在 $[1, n]$ 范围内，有多少个整数可以表示成某个素数的方幂。

解题思路

这个问题的核心是高效地找出并统计所有小于等于 $n$ 的素数幂。

一个低效的方法是遍历从 1 到 $n$ 的每个数，并逐一判断它是否为素数幂。判断一个数 $x$ 是否为素数幂，需要对其进行质因数分解，看其是否只有一个唯一的质因子，这个过程复杂度较高，整体效率不佳。

一个更高效的策略是生成法：我们不逐一检查，而是直接生成所有小于等于 $n$ 的素数幂。

算法流程：

筛选素数：
- 首先，我们需要找到所有小于等于 $n$ 的素数，作为生成素数幂的“底”。
- 使用埃拉托斯特尼筛法 (Sieve of Eratosthenes) 是最高效的方法。创建一个大小为 $n+1$ 的布尔数组 is_prime，初始化所有值为 true。然后从 2 开始，将所有素数的倍数标记为 false。
生成并存储素数幂：
- 创建一个集合 (Set)，用于存储所有找到的素数幂。使用集合可以自动处理重复值（虽然在本问题中一个数只可能是唯一一个素数的幂）。
- 遍历从 2 到 $n$ 的所有整数。如果一个数 $p$ 在筛法步骤后被确定为素数（即 is_prime[p] 为 true）： a. 从这个素数 $p$ 开始，生成它的幂次： $p^1, p^2, p^3, \dots$ 。 b. 将每个生成的幂次 power 添加到集合中。 c. 当 power 超过 $n$ 时，停止为这个素数 $p$ 生成后续的幂次。
- 为了防止在计算 power * p 时发生整数溢出，可以在乘法前进行检查，例如 if (power > n / p)。
统计结果：
- 所有素数遍历完毕后，集合的大小就是最终的答案。
- 注意，数字 1 不是任何素数的幂，所以我们的遍历从 2 开始即可，并且最终结果自然也不包含 1。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n < 2) {
        cout << 0 << endl;
        return 0;
    }

    // 1. 埃氏筛法找出所有素数
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 2. 生成所有素数幂并用集合存储
    set<ll> prime_powers;
    for (int p = 2; p <= n; ++p) {
        if (is_prime[p]) {
            ll power = p;
            while (power <= n) {
                prime_powers.insert(power);
                // 防止溢出
                if (power > n / p) {
                    break;
                }
                power *= p;
            }
        }
    }

    // 3. 输出集合大小
    cout << prime_powers.size() << endl;

    return 0;
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n < 2) {
            System.out.println(0);
            return;
        }

        // 1. 埃氏筛法找出所有素数
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // 2. 生成所有素数幂并用集合存储
        Set<Long> primePowers = new HashSet<>();
        for (int p = 2; p <= n; p++) {
            if (isPrime[p]) {
                long power = p;
                while (power <= n) {
                    primePowers.add(power);
                    // 防止溢出
                    if (power > n / p) {
                        break;
                    }
                    power *= p;
                }
            }
        }

        // 3. 输出集合大小
        System.out.println(primePowers.size());
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)

        if n < 2:
            print(0)
            return

        # 1. 埃氏筛法找出所有素数
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for p in range(2, int(n**0.5) + 1):
            if is_prime[p]:
                for i in range(p * p, n + 1, p):
                    is_prime[i] = False

        # 2. 生成所有素数幂并用集合存储
        prime_powers = set()
        for p in range(2, n + 1):
            if is_prime[p]:
                power = p
                while power <= n:
                    prime_powers.add(power)
                    power *= p
        
        # 3. 输出集合大小
        print(len(prime_powers))

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数论、埃拉托斯特尼筛法
时间复杂度： $\mathcal{O}(N \log \log N)$ 。算法的瓶颈在于埃氏筛法，其时间复杂度为 $\mathcal{O}(N \log \log N)$ 。后续生成素数幂的循环总执行次数远小于 $N \log N$ ，因此总时间复杂度由筛法决定。
空间复杂度： $\mathcal{O}(N)$ 。需要一个大小为 $N$ 的布尔数组来进行素数筛选。存储素数幂的集合大小不会超过 $N$ 。