质数是数论的基础，在加密算法、哈希表设计、随机数生成等领域有重要应用。质数判断与筛选器支持单个数字质数判断、质因数分解以及使用埃拉托斯特尼筛法批量筛选范围内的所有质数，并提供质数间距、孪生质数对等统计分析功能。

本案例基于 Kotlin Multiplatform（KMP）与 OpenHarmony，实现了一个质数判断与筛选器：

• 质数判断：快速判断单个数字是否为质数（试除法，O(√n)）
• 质因数分解：将合数分解为质因数的乘积形式
• 批量筛选：使用埃拉托斯特尼筛法筛选范围内的所有质数（O(n log log n)）
• 统计分析：质数间距、孪生质数对、质数密度等特征分析

---

一、问题背景与典型场景

典型场景：

1. 加密算法：RSA 公钥加密算法需要大质数，质数判断是生成密钥对的基础
2. 哈希表设计：使用质数作为哈希表大小可减少冲突
3. 随机数生成：质数模运算在伪随机数生成器中常用
4. 数学研究：质数分布、孪生质数猜想等数论研究
5. 教学演示：理解质数概念、筛选算法的经典案例

优势：

• 算法经典：埃拉托斯特尼筛法是最古老的筛选算法之一，思路清晰
• 效率高：筛法的时间复杂度为 O(n log log n)，远优于逐个判断的 O(n√n)
• 实用性强：质数在计算机科学的多个领域有广泛应用
• 可扩展：可扩展为 Miller-Rabin 素性测试、Pollard’s rho 分解等高级算法

---

二、质数判断原理拆解

2.1 试除法判断质数

判断一个数 n 是否为质数的经典方法是试除法：

算法步骤：

1. 如果 n < 2，则不是质数
2. 如果 n == 2，则是质数
3. 如果 n 是偶数（n % 2 == 0），则不是质数
4. 从 3 开始，检查所有奇数 i 是否能整除 n（仅需检查到 √n）
5. 如果存在 i 能整除 n，则 n 是合数；否则 n 是质数

时间复杂度：O(√n)

优化技巧：

• 跳过偶数，只检查奇数
• 只检查到 √n，因为如果 n 有大于 √n 的因子，必有小于 √n 的因子

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    if (n == 2) return true
    if (n % 2 == 0) return false
    
    var i = 3
    while (i * i <= n) {
        if (n % i == 0) return false
        i += 2
    }
    return true
}

2.2 质因数分解

将一个合数分解为质因数的乘积：

算法步骤：

1. 从最小的质数 2 开始
2. 如果当前质数能整除 n，则记录该质数，并将 n 除以该质数
3. 重复步骤 2，直到该质数不能整除 n
4. 移动到下一个质数（或奇数），重复步骤 2-3
5. 直到 n 变为 1 或当前质数的平方大于 n

时间复杂度：O(√n)

fun primeFactors(n: Int): List<Int> {
    val factors = mutableListOf<Int>()
    var num = n
    var i = 2
    
    while (i * i <= num) {
        while (num % i == 0) {
            factors += i
            num /= i
        }
        i++
    }
    if (num > 1) {
        factors += num
    }
    return factors
}

---

三、埃拉托斯特尼筛法原理

埃拉托斯特尼筛法（Sieve of Eratosthenes）是筛选质数的经典算法，由古希腊数学家埃拉托斯特尼在公元前 2 世纪提出。

3.1 算法原理

核心思想：从 2 开始，将每个质数的倍数都标记为合数。

算法步骤：

1. 创建一个布尔数组 isPrime[0..n]，初始化为 true
2. 标记 0 和 1 为非质数（false）
3. 从 2 开始遍历到 √n：
   • 如果 isPrime[i] 为 true，则 i 是质数
   • 将 i 的所有倍数（i², i²+i, i²+2i, …）标记为 false
4. 遍历完成后，所有 isPrime[i] == true 的 i 都是质数

时间复杂度：O(n log log n)
空间复杂度：O(n)

3.2 算法优化

1. 从 i² 开始标记：因为小于 i² 的 i 的倍数已经被更小的质数标记过了
2. 只标记奇数倍数：偶数已经在 2 的倍数中被标记，可以跳过

fun sieveOfEratosthenes(limit: Int): List<Int> {
    if (limit < 2) return emptyList()
    
    val isPrime = BooleanArray(limit + 1) { true }
    isPrime[0] = false
    isPrime[1] = false
    
    var i = 2
    while (i * i <= limit) {
        if (isPrime[i]) {
            var j = i * i
            while (j <= limit) {
                isPrime[j] = false
                j += i
            }
        }
        i++
    }
    
    val result = mutableListOf<Int>()
    for (i in isPrime.indices) {
        if (isPrime[i]) {
            result.add(i)
        }
    }
    return result
}

3.3 算法复杂度分析

时间复杂度推导：

• 对于每个质数 p ≤ √n，需要标记 n/p 个数
• 总标记次数约为：n/2 + n/3 + n/5 + n/7 + … + n/p_max
• 这是调和级数的变种，近似为 n × (1/2 + 1/3 + 1/5 + …)
• 质数倒数和约为 log log n，所以总复杂度为 O(n log log n)

空间复杂度：需要 O(n) 的布尔数组存储标记

---

四、Kotlin 实现详解

4.1 质数判断实现

fun isPrime(n: Int): Boolean {
    if (n < 2) return false
    if (n == 2) return true
    if (n % 2 == 0) return false
    
    var i = 3
    while (i * i <= n) {
        if (n % i == 0) return false
        i += 2
    }
    return true
}

关键点：

• 快速处理边界情况（< 2, == 2, 偶数）
• 只检查奇数因子
• 仅检查到 √n

4.2 质因数分解实现

fun primeFactors(n: Int): List<Int> {
    if (n < 2) return emptyList()
    val factors = mutableListOf<Int>()
    var num = n
    var i = 2
    
    while (i * i <= num) {
        while (num % i == 0) {
            factors += i
            num /= i
        }
        i++
    }
    if (num > 1) {
        factors += num
    }
    return factors
}

关键点：

• 内层循环处理同一个质数的多次幂
• 最后检查剩余的 num 是否为质数

4.3 埃拉托斯特尼筛法实现

fun sieveOfEratosthenes(limit: Int): List<Int> {
    if (limit < 2) return emptyList()
    
    val isPrime = BooleanArray(limit + 1) { true }
    isPrime[0] = false
    isPrime[1] = false
    
    var i = 2
    while (i * i <= limit) {
        if (isPrime[i]) {
            var j = i * i
            while (j <= limit) {
                isPrime[j] = false
                j += i
            }
        }
        i++
    }
    
    val result = mutableListOf<Int>()
    for (i in isPrime.indices) {
        if (isPrime[i]) {
            result.add(i)
        }
    }
    return result
}

关键点：

• 使用布尔数组标记，节省空间
• 从 i² 开始标记，避免重复
• 只遍历到 √limit

4.4 输入解析与结果输出

@JsExport
fun primeNumberCheckerAndSieve(inputData: String): String {
    // 解析输入：range=1,100 或 number=17
    // 根据输入类型调用相应的函数
    // 格式化输出结果
}

输入格式支持：

• range=1,100：筛选范围内的质数
• number=17：判断单个数字是否为质数

输出内容：

• 质数列表（按行显示，每行10个）
• 质数数量、密度统计
• 相邻质数间距分析
• 孪生质数对（相邻质数间距为2）

---

五、ArkTS 前端集成

5.1 页面布局设计

采用垂直卡片式布局，紫色主题：

Column() {
  // 顶部标题栏
  Row() {
    Text("🔢 质数判断与筛选器")
      .fontSize(22)
      .fontWeight(FontWeight.Bold)
      .fontColor(Color.White)
  }
  .width('100%')
  .height(50)
  .backgroundColor('#7B1FA2') // 紫色主题

  Scroll() {
    Column() {
      // 功能介绍卡片
      // 输入区域卡片
      // 执行按钮
      // 结果显示区域
    }
  }
}

5.2 功能模块

1. 输入区域：

   • TextArea 用于输入参数
   • 快捷按钮：范围示例、质数判断、大范围、清除

2. 执行逻辑：

   private executeCase() {
     this.isLoading = true
     setTimeout(() => {
       try {
         let output: string = primeNumberCheckerAndSieve(this.inputValue)
         this.result = output
       } catch (error) {
         this.result = `❌ 执行出错: ${error}`
       } finally {
         this.isLoading = false
       }
     }, 100)
   }
   

3. 结果显示：

   • 使用 Scroll 包裹 Text 显示格式化结果
   • 等宽字体（fontFamily('monospace')）保持对齐

5.3 用户交互

• 快捷填充：一键填入常用示例
• 实时反馈：加载状态指示器
• 错误处理：捕获异常并显示友好错误信息

---

六、工程化应用

6.1 性能优化

1. 筛法优化：

   • 使用布尔数组而非整型数组，节省空间
   • 从 i² 开始标记，减少重复操作
   • 只遍历到 √n

2. 大数处理：

   • 限制范围上限（如 10000），避免内存溢出
   • 对于更大的范围，可考虑分段筛法（Segmented Sieve）

3. 质数判断优化：

   • 快速排除偶数
   • 只检查到 √n

6.2 扩展功能

1. Miller-Rabin 素性测试：

   • 概率性算法，适合大数判断
   • 时间复杂度 O(k log³ n)，k 为测试次数

2. 分段筛法：

   • 处理大范围质数筛选
   • 分段处理，降低内存占用

3. 质数生成器：

   • 按需生成下一个质数
   • 可用于密钥生成场景

4. 质数间距分析：

   • 分析质数间隙的分布
   • 研究孪生质数、三生质数等

6.3 实际应用场景

1. 加密算法：

   • RSA 密钥生成需要大质数
   • 质数判断是密钥生成的关键步骤

2. 哈希表设计：

   • 使用质数作为哈希表大小可减少冲突
   • 常用的质数：31, 131, 1313, 13131 等

3. 随机数生成：

   • 线性同余生成器使用质数模数
   • 质数模运算具有良好的统计特性

4. 数据分布：

   • 质数可用于数据分片、负载均衡
   • 利用质数的分布特性实现均匀分配

5. 数学研究：

   • 质数分布规律（素数定理）
   • 孪生质数猜想、哥德巴赫猜想等

---

七、总结

质数判断与筛选器展示了：

• 经典算法：埃拉托斯特尼筛法是数论与算法教学的经典案例
• 高效实现：O(n log log n) 的时间复杂度，远优于逐个判断
• 实用价值：质数在加密、哈希、随机数生成等领域有重要应用
• 扩展性强：可扩展为 Miller-Rabin 测试、分段筛法等高级算法

通过 KMP 与 OpenHarmony 的集成，实现了跨平台的质数工具，可用于教学演示、算法研究以及实际应用开发。

---

相关技术栈：

• Kotlin Multiplatform（KMP）
• OpenHarmony / ArkTS
• 埃拉托斯特尼筛法
• 试除法
• 质因数分解

应用领域：

• 加密算法
• 哈希表设计
• 随机数生成
• 数论研究
• 算法教学

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net