文章概述

质数检查（Prime Number Check）是数论中最基础且最重要的问题之一，也是许多密码学算法的基础。这个问题要求判断一个给定的整数是否是质数。虽然问题定义简单，但其解决方案涉及多种不同的算法思想，从暴力枚举到高效的概率性测试，再到现代的确定性算法，每种方法都展现了算法优化的不同阶段。

质数检查问题在实际应用中有广泛的用途。在密码学中，质数是RSA加密、椭圆曲线密码学等算法的基础。在数据结构中，质数用于设计哈希表的大小以减少碰撞。在随机数生成中，质数用于构造伪随机数生成器。在数学研究中，质数的性质一直是研究的热点。在计算机安全中，大质数的生成和验证对系统安全至关重要。

本文将深入探讨如何在KMP（Kotlin Multiplatform）框架下实现质数检查问题的多种解决方案，并展示如何在OpenHarmony鸿蒙平台上进行跨端调用。我们将对比不同算法的时间复杂度、空间复杂度和实际性能，帮助开发者选择最合适的方案。

算法原理详解

问题定义

给定一个正整数，判断它是否是质数。质数是指只能被1和自身整除的大于1的自然数。

例如：

• 输入：n = 17
• 输出：true
• 解释：17只能被1和17整除

另一个例子：

• 输入：n = 1
• 输出：false
• 解释：1不是质数

解决方案对比

方案1：暴力枚举法（Brute Force）

最直观的方法是从2开始，逐个检查每个数是否能整除n。这种方法的优点是实现简单，缺点是时间复杂度较高。

时间复杂度：O(n)
空间复杂度：O(1)
优点：实现简单，易于理解
缺点：性能较差，不适合大数值
适用场景：数值较小的场景

方案2：优化枚举法（Optimized Enumeration）

通过观察，我们只需要检查到√n即可，因为如果n有大于√n的因子，它必然有小于√n的因子。这种方法的优点是性能相对较好，缺点是仍需要遍历。

时间复杂度：O(√n)
空间复杂度：O(1)
优点：性能相对较好，实现简单
缺点：对于大数值仍然较慢
适用场景：中等大小的数值

方案3：6k±1优化法（6k±1 Optimization）

利用所有质数（除了2和3）都可以表示为6k±1的形式这一性质，可以进一步优化检查过程。这种方法的优点是性能更好，缺点是实现相对复杂。

时间复杂度：O(√n)
空间复杂度：O(1)
优点：性能优异，实现相对简单
缺点：需要理解6k±1的性质
适用场景：中等到大型的数值

方案4：Miller-Rabin素性测试（Miller-Rabin Primality Test）

这是一种概率性的素性测试算法，对于大数值非常有效。这种方法的优点是对于大数值性能优异，缺点是结果是概率性的。

时间复杂度：O(k log³ n)，其中k是测试次数
空间复杂度：O(1)
优点：对于大数值性能优异，广泛应用于密码学
缺点：结果是概率性的
适用场景：大数值的素性测试

方案5：埃拉托斯特尼筛法（Sieve of Eratosthenes）

这是一种用于找出所有小于等于n的质数的算法。这种方法的优点是可以一次性找出所有质数，缺点是需要额外的空间。

时间复杂度：O(n log log n)
空间复杂度：O(n)
优点：可以找出所有质数，对于批量检查高效
缺点：需要额外的空间
适用场景：需要找出一定范围内所有质数的场景

算法选择指南

• 单个小数值：使用优化枚举法
• 单个中等数值：使用6k±1优化法（推荐）
• 单个大数值：使用Miller-Rabin测试
• 需要找出所有质数：使用埃拉托斯特尼筛法
• 需要快速判断：使用6k±1优化法

Kotlin实现

完整的Kotlin代码实现

/**
 * 质数检查(Prime Number Check)算法工具类 - KMP OpenHarmony
 * 提供多种解决方案来检查一个数是否是质数
 */
object PrimeUtils {
    
    /**
     * 方案1：暴力枚举法
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 从2开始逐个检查每个数是否能整除n
     */
    fun isPrimeBruteForce(n: Int): Boolean {
        if (n < 2) return false
        if (n == 2) return true
        if (n % 2 == 0) return false
        
        for (i in 3 until n step 2) {
            if (n % i == 0) return false
        }
        
        return true
    }
    
    /**
     * 方案2：优化枚举法
     * 时间复杂度：O(√n)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 只需要检查到√n，因为如果n有大于√n的因子，
     * 它必然有小于√n的因子
     */
    fun isPrimeOptimized(n: Int): Boolean {
        if (n < 2) return false
        if (n == 2) return true
        if (n % 2 == 0) return false
        
        val sqrtN = Math.sqrt(n.toDouble()).toInt()
        
        for (i in 3..sqrtN step 2) {
            if (n % i == 0) return false
        }
        
        return true
    }
    
    /**
     * 方案3：6k±1优化法（推荐）
     * 时间复杂度：O(√n)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 所有质数（除了2和3）都可以表示为6k±1的形式
     * 因此只需要检查这些形式的数
     */
    fun isPrime6k(n: Int): Boolean {
        if (n <= 1) return false
        if (n <= 3) return true
        if (n % 2 == 0 || n % 3 == 0) return false
        
        var i = 5
        while (i * i <= n) {
            if (n % i == 0 || n % (i + 2) == 0) return false
            i += 6
        }
        
        return true
    }
    
    /**
     * 方案4：Miller-Rabin素性测试
     * 时间复杂度：O(k log³ n)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 一种概率性的素性测试算法
     * 对于大数值非常有效
     */
    fun isMillerRabin(n: Long, k: Int = 5): Boolean {
        if (n < 2) return false
        if (n == 2 || n == 3) return true
        if (n % 2 == 0) return false
        
        // 将n-1表示为2^r * d的形式
        var d = n - 1
        var r = 0
        while (d % 2 == 0) {
            d /= 2
            r++
        }
        
        // 进行k次测试
        repeat(k) {
            val a = 2 + (Math.random() * (n - 3)).toLong()
            var x = modPow(a, d, n)
            
            if (x == 1L || x == n - 1) return@repeat
            
            var composite = true
            repeat(r - 1) {
                x = (x * x) % n
                if (x == n - 1) {
                    composite = false
                    return@repeat
                }
            }
            
            if (composite) return false
        }
        
        return true
    }
    
    /**
     * 模幂运算
     */
    private fun modPow(base: Long, exp: Long, mod: Long): Long {
        var result = 1L
        var b = base % mod
        var e = exp
        
        while (e > 0) {
            if (e % 2 == 1L) {
                result = (result * b) % mod
            }
            b = (b * b) % mod
            e /= 2
        }
        
        return result
    }
    
    /**
     * 方案5：埃拉托斯特尼筛法
     * 时间复杂度：O(n log log n)
     * 空间复杂度：O(n)
     */
    fun sieveOfEratosthenes(n: Int): List<Int> {
        if (n < 2) return emptyList()
        
        val isPrime = BooleanArray(n + 1) { true }
        isPrime[0] = false
        isPrime[1] = false
        
        for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
            if (isPrime[i]) {
                for (j in i * i..n step i) {
                    isPrime[j] = false
                }
            }
        }
        
        return (2..n).filter { isPrime[it] }
    }
    
    /**
     * 性能演示函数 - 对比多种方法的性能
     */
    fun performanceDemo(): String {
        val result = StringBuilder()
        result.append("质数检查性能对比 (测试10000个数字)\n")
        result.append("=".repeat(70)).append("\n\n")
        
        val testNumbers = (1..10000).toList()
        
        // 方案1：暴力枚举法（仅对小数据集）
        val smallTestNumbers = testNumbers.filter { it < 1000 }
        if (smallTestNumbers.isNotEmpty()) {
            val time1 = measureTimeMillis {
                smallTestNumbers.forEach { isPrimeBruteForce(it) }
            }
            result.append("方案1 - 暴力枚举法\n")
            result.append("耗时: ${time1}ms (仅测试小数据集)\n")
            result.append("时间复杂度: O(n)\n\n")
        } else {
            result.append("方案1 - 暴力枚举法\n")
            result.append("耗时: 跳过（数据太大）\n\n")
        }
        
        // 方案2：优化枚举法
        val time2 = measureTimeMillis {
            testNumbers.forEach { isPrimeOptimized(it) }
        }
        result.append("方案2 - 优化枚举法\n")
        result.append("耗时: ${time2}ms\n")
        result.append("时间复杂度: O(√n)\n\n")
        
        // 方案3：6k±1优化法
        val time3 = measureTimeMillis {
            testNumbers.forEach { isPrime6k(it) }
        }
        result.append("方案3 - 6k±1优化法（推荐）\n")
        result.append("耗时: ${time3}ms\n")
        result.append("时间复杂度: O(√n)\n\n")
        
        // 方案4：Miller-Rabin测试
        val time4 = measureTimeMillis {
            testNumbers.forEach { isMillerRabin(it.toLong()) }
        }
        result.append("方案4 - Miller-Rabin测试\n")
        result.append("耗时: ${time4}ms\n")
        result.append("时间复杂度: O(k log³ n)\n\n")
        
        // 方案5：埃拉托斯特尼筛法
        val time5 = measureTimeMillis {
            sieveOfEratosthenes(10000)
        }
        result.append("方案5 - 埃拉托斯特尼筛法\n")
        result.append("耗时: ${time5}ms\n")
        result.append("时间复杂度: O(n log log n)\n\n")
        
        // 性能对比
        result.append("性能对比总结\n")
        result.append("-".repeat(70)).append("\n")
        result.append("最快方案: 6k±1优化法\n")
        result.append("推荐方案: 6k±1优化法（综合考虑性能和实现复杂度）\n")
        
        return result.toString()
    }
}

// 扩展函数
fun Int.isPrime(): Boolean {
    return PrimeUtils.isPrime6k(this)
}

// 使用示例
fun main() {
    println("KMP OpenHarmony 质数检查(Prime Number Check)算法演示\n")
    
    val testNumbers = listOf(2, 3, 4, 17, 20, 97, 100, 1009)
    
    println("测试数字: ${testNumbers.joinToString(", ")}\n")
    
    for (num in testNumbers) {
        println("数字: $num")
        
        // 方案1
        val result1 = PrimeUtils.isPrimeBruteForce(num)
        println("  方案1 - 暴力枚举法: $result1")
        
        // 方案2
        val result2 = PrimeUtils.isPrimeOptimized(num)
        println("  方案2 - 优化枚举法: $result2")
        
        // 方案3
        val result3 = PrimeUtils.isPrime6k(num)
        println("  方案3 - 6k±1优化法: $result3")
        
        // 方案4
        val result4 = PrimeUtils.isMillerRabin(num.toLong())
        println("  方案4 - Miller-Rabin测试: $result4")
        
        println()
    }
    
    println("找出100以内的所有质数:")
    val primes = PrimeUtils.sieveOfEratosthenes(100)
    println(primes.joinToString(", "))
    
    println("\n性能演示:")
    println(PrimeUtils.performanceDemo())
}

fun measureTimeMillis(block: () -> Unit): Long {
    val start = System.currentTimeMillis()
    block()
    return System.currentTimeMillis() - start
}

Kotlin实现的详细说明

Kotlin实现提供了五种不同的质数检查方案。暴力枚举法虽然时间复杂度较高，但在数值较小时仍然是可行的，并且代码最为简洁。优化枚举法通过只检查到√n来提高性能。

6k±1优化法是最实用的方案，它利用了质数的数学性质来进一步优化检查过程。Miller-Rabin测试是一种概率性的算法，对于大数值非常有效，广泛应用于密码学。埃拉托斯特尼筛法可以一次性找出所有质数，对于批量检查非常高效。

JavaScript实现

完整的JavaScript代码实现

/**
 * 质数检查(Prime Number Check)算法工具类 - JavaScript版本
 * 用于在Web和Node.js环境中使用
 */
class PrimeJS {
    /**
     * 方案1：暴力枚举法
     * @param {number} n - 输入数字
     * @returns {boolean} 是否是质数
     */
    static isPrimeBruteForce(n) {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        
        for (let i = 3; i < n; i += 2) {
            if (n % i === 0) return false;
        }
        
        return true;
    }
    
    /**
     * 方案2：优化枚举法
     * @param {number} n - 输入数字
     * @returns {boolean} 是否是质数
     */
    static isPrimeOptimized(n) {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        
        const sqrtN = Math.floor(Math.sqrt(n));
        
        for (let i = 3; i <= sqrtN; i += 2) {
            if (n % i === 0) return false;
        }
        
        return true;
    }
    
    /**
     * 方案3：6k±1优化法（推荐）
     * @param {number} n - 输入数字
     * @returns {boolean} 是否是质数
     */
    static isPrime6k(n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 === 0 || n % 3 === 0) return false;
        
        let i = 5;
        while (i * i <= n) {
            if (n % i === 0 || n % (i + 2) === 0) return false;
            i += 6;
        }
        
        return true;
    }
    
    /**
     * 方案4：Miller-Rabin素性测试
     * @param {number} n - 输入数字
     * @param {number} k - 测试次数
     * @returns {boolean} 是否是质数
     */
    static isMillerRabin(n, k = 5) {
        if (n < 2) return false;
        if (n === 2 || n === 3) return true;
        if (n % 2 === 0) return false;
        
        // 将n-1表示为2^r * d的形式
        let d = n - 1;
        let r = 0;
        while (d % 2 === 0) {
            d = Math.floor(d / 2);
            r++;
        }
        
        // 进行k次测试
        for (let i = 0; i < k; i++) {
            const a = 2 + Math.floor(Math.random() * (n - 3));
            let x = this.modPow(a, d, n);
            
            if (x === 1 || x === n - 1) continue;
            
            let composite = true;
            for (let j = 0; j < r - 1; j++) {
                x = (x * x) % n;
                if (x === n - 1) {
                    composite = false;
                    break;
                }
            }
            
            if (composite) return false;
        }
        
        return true;
    }
    
    /**
     * 模幂运算
     */
    static modPow(base, exp, mod) {
        let result = 1;
        let b = base % mod;
        let e = exp;
        
        while (e > 0) {
            if (e % 2 === 1) {
                result = (result * b) % mod;
            }
            b = (b * b) % mod;
            e = Math.floor(e / 2);
        }
        
        return result;
    }
    
    /**
     * 方案5：埃拉托斯特尼筛法
     * @param {number} n - 上限
     * @returns {number[]} 所有质数
     */
    static sieveOfEratosthenes(n) {
        if (n < 2) return [];
        
        const isPrime = new Array(n + 1).fill(true);
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        const primes = [];
        for (let i = 2; i <= n; i++) {
            if (isPrime[i]) primes.push(i);
        }
        
        return primes;
    }
    
    /**
     * 性能演示函数
     * @returns {string} 性能报告
     */
    static performanceDemo() {
        let result = `质数检查性能对比 (测试10000个数字)\n`;
        result += '='.repeat(70) + '\n\n';
        
        const testNumbers = Array.from({ length: 10000 }, (_, i) => i + 1);
        
        // 方案1
        const smallTestNumbers = testNumbers.filter(n => n < 1000);
        if (smallTestNumbers.length > 0) {
            const start1 = performance.now();
            smallTestNumbers.forEach(n => PrimeJS.isPrimeBruteForce(n));
            const time1 = performance.now() - start1;
            result += `方案1 - 暴力枚举法: ${time1.toFixed(2)}ms (仅测试小数据集)\n`;
            result += '时间复杂度: O(n)\n\n';
        } else {
            result += `方案1 - 暴力枚举法: 跳过（数据太大）\n\n`;
        }
        
        // 方案2
        const start2 = performance.now();
        testNumbers.forEach(n => PrimeJS.isPrimeOptimized(n));
        const time2 = performance.now() - start2;
        result += `方案2 - 优化枚举法: ${time2.toFixed(2)}ms\n`;
        result += '时间复杂度: O(√n)\n\n';
        
        // 方案3
        const start3 = performance.now();
        testNumbers.forEach(n => PrimeJS.isPrime6k(n));
        const time3 = performance.now() - start3;
        result += `方案3 - 6k±1优化法（推荐）: ${time3.toFixed(2)}ms\n`;
        result += '时间复杂度: O(√n)\n\n';
        
        // 方案4
        const start4 = performance.now();
        testNumbers.forEach(n => PrimeJS.isMillerRabin(n));
        const time4 = performance.now() - start4;
        result += `方案4 - Miller-Rabin测试: ${time4.toFixed(2)}ms\n`;
        result += '时间复杂度: O(k log³ n)\n\n';
        
        // 方案5
        const start5 = performance.now();
        PrimeJS.sieveOfEratosthenes(10000);
        const time5 = performance.now() - start5;
        result += `方案5 - 埃拉托斯特尼筛法: ${time5.toFixed(2)}ms\n`;
        result += '时间复杂度: O(n log log n)\n\n';
        
        result += '性能对比总结\n';
        result += '-'.repeat(70) + '\n';
        result += '最快方案: 6k±1优化法\n';
        result += '推荐方案: 6k±1优化法（综合考虑性能和实现复杂度）\n';
        
        return result;
    }
}

// 导出供Node.js使用
if (typeof module !== 'undefined' && module.exports) {
    module.exports = PrimeJS;
}

JavaScript实现的详细说明

JavaScript版本的实现与Kotlin版本在逻辑上完全一致，但充分利用了JavaScript的语言特性。在模幂运算中，我们使用了位运算和模运算来实现高效的计算。在埃拉托斯特尼筛法中，我们使用了数组和循环来实现。

JavaScript的performance.now()方法提供了微秒级的精度，使得性能测试更加准确。在实际应用中，开发者可以使用这个性能演示函数来选择最适合的算法。

ArkTS调用实现

完整的ArkTS代码实现

/**
 * 质数检查(Prime Number Check)工具 - ArkTS版本（OpenHarmony鸿蒙）
 * 用于在鸿蒙应用中实现质数检查算法
 */
import { webview } from '@kit.ArkWeb';
import { common } from '@kit.AbilityKit';

@Entry
@Component
struct PrimeCheckPage {
    @State inputNumber: string = '17';
    @State result: string = '';
    @State selectedMethod: string = '6k±1优化法';
    @State isLoading: boolean = false;
    @State allResults: string = '';
    @State primeList: string = '';
    @State performanceData: string = '';
    @State showPerformance: boolean = false;
    
    // Web视图控制器
    webviewController: webview.WebviewController = new webview.WebviewController();
    
    /**
     * 方案1：暴力枚举法
     */
    isPrimeBruteForce(n: number): boolean {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        
        for (let i = 3; i < n; i += 2) {
            if (n % i === 0) return false;
        }
        
        return true;
    }
    
    /**
     * 方案2：优化枚举法
     */
    isPrimeOptimized(n: number): boolean {
        if (n < 2) return false;
        if (n === 2) return true;
        if (n % 2 === 0) return false;
        
        const sqrtN = Math.floor(Math.sqrt(n));
        
        for (let i = 3; i <= sqrtN; i += 2) {
            if (n % i === 0) return false;
        }
        
        return true;
    }
    
    /**
     * 方案3：6k±1优化法（推荐）
     */
    isPrime6k(n: number): boolean {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 === 0 || n % 3 === 0) return false;
        
        let i = 5;
        while (i * i <= n) {
            if (n % i === 0 || n % (i + 2) === 0) return false;
            i += 6;
        }
        
        return true;
    }
    
    /**
     * 方案4：Miller-Rabin素性测试
     */
    isMillerRabin(n: number, k: number = 5): boolean {
        if (n < 2) return false;
        if (n === 2 || n === 3) return true;
        if (n % 2 === 0) return false;
        
        let d = n - 1;
        let r = 0;
        while (d % 2 === 0) {
            d = Math.floor(d / 2);
            r++;
        }
        
        for (let i = 0; i < k; i++) {
            const a = 2 + Math.floor(Math.random() * (n - 3));
            let x = this.modPow(a, d, n);
            
            if (x === 1 || x === n - 1) continue;
            
            let composite = true;
            for (let j = 0; j < r - 1; j++) {
                x = (x * x) % n;
                if (x === n - 1) {
                    composite = false;
                    break;
                }
            }
            
            if (composite) return false;
        }
        
        return true;
    }
    
    /**
     * 模幂运算
     */
    modPow(base: number, exp: number, mod: number): number {
        let result = 1;
        let b = base % mod;
        let e = exp;
        
        while (e > 0) {
            if (e % 2 === 1) {
                result = (result * b) % mod;
            }
            b = (b * b) % mod;
            e = Math.floor(e / 2);
        }
        
        return result;
    }
    
    /**
     * 埃拉托斯特尼筛法
     */
    sieveOfEratosthenes(n: number): number[] {
        if (n < 2) return [];
        
        const isPrime = new Array(n + 1).fill(true);
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        const primes: number[] = [];
        for (let i = 2; i <= n; i++) {
            if (isPrime[i]) primes.push(i);
        }
        
        return primes;
    }
    
    /**
     * 执行质数检查
     */
    async executePrimeCheck() {
        this.isLoading = true;
        this.showPerformance = false;
        
        try {
            const num = parseInt(this.inputNumber);
            
            if (isNaN(num) || num < 1) {
                this.result = '错误：请输入有效的正整数';
                this.isLoading = false;
                return;
            }
            
            let isPrime = false;
            
            switch (this.selectedMethod) {
                case '暴力枚举法':
                    isPrime = this.isPrimeBruteForce(num);
                    break;
                case '优化枚举法':
                    isPrime = this.isPrimeOptimized(num);
                    break;
                case '6k±1优化法':
                    isPrime = this.isPrime6k(num);
                    break;
                case 'Miller-Rabin测试':
                    isPrime = this.isMillerRabin(num);
                    break;
            }
            
            this.result = `数字: ${num}\n` +
                `是否是质数: ${isPrime ? '是' : '否'}`;
            
            // 同时显示所有方法的结果
            const results = [
                `暴力枚举法: ${this.isPrimeBruteForce(num)}`,
                `优化枚举法: ${this.isPrimeOptimized(num)}`,
                `6k±1优化法: ${this.isPrime6k(num)}`,
                `Miller-Rabin测试: ${this.isMillerRabin(num)}`
            ];
            this.allResults = `所有方法的结果:\n${results.join('\n')}`;
            
            // 显示100以内的质数
            const primes = this.sieveOfEratosthenes(100);
            this.primeList = `100以内的质数 (共${primes.length}个):\n${primes.slice(0, 20).join(', ')}${primes.length > 20 ? ', ...' : ''}`;
        } catch (error) {
            this.result = '计算错误：' + error;
        }
        
        this.isLoading = false;
    }
    
    /**
     * 执行性能演示
     */
    async executePerformanceDemo() {
        this.isLoading = true;
        this.showPerformance = true;
        
        try {
            const testNumbers = Array.from({ length: 10000 }, (_, i) => i + 1);
            
            let result = `质数检查性能对比 (测试10000个数字)\n`;
            result += '='.repeat(70) + '\n\n';
            
            // 方案2
            const start2 = Date.now();
            testNumbers.forEach(n => this.isPrimeOptimized(n));
            const time2 = Date.now() - start2;
            result += `方案2 - 优化枚举法: ${time2}ms\n`;
            result += '时间复杂度: O(√n)\n\n';
            
            // 方案3
            const start3 = Date.now();
            testNumbers.forEach(n => this.isPrime6k(n));
            const time3 = Date.now() - start3;
            result += `方案3 - 6k±1优化法: ${time3}ms\n`;
            result += '时间复杂度: O(√n)\n\n';
            
            // 方案4
            const start4 = Date.now();
            testNumbers.forEach(n => this.isMillerRabin(n));
            const time4 = Date.now() - start4;
            result += `方案4 - Miller-Rabin测试: ${time4}ms\n`;
            result += '时间复杂度: O(k log³ n)\n\n';
            
            // 方案5
            const start5 = Date.now();
            this.sieveOfEratosthenes(10000);
            const time5 = Date.now() - start5;
            result += `方案5 - 埃拉托斯特尼筛法: ${time5}ms\n`;
            result += '时间复杂度: O(n log log n)\n\n';
            
            result += '性能对比总结\n';
            result += '-'.repeat(70) + '\n';
            result += '最快方案: 6k±1优化法\n';
            result += '推荐方案: 6k±1优化法（综合考虑性能和实现复杂度）\n';
            
            this.performanceData = result;
        } catch (error) {
            this.performanceData = '演示失败：' + error;
        }
        
        this.isLoading = false;
    }
    
    build() {
        Column() {
            // 顶部栏
            Row() {
                Text('质数检查(Prime Number Check)')
                    .fontSize(24)
                    .fontWeight(FontWeight.Bold)
                    .fontColor(Color.White)
            }
            .width('100%')
            .height(60)
            .backgroundColor('#1565C0')
            .justifyContent(FlexAlign.Center)
            
            // 主内容
            Scroll() {
                Column({ space: 16 }) {
                    // 输入数字
                    Column() {
                        Text('输入数字:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        TextInput({ placeholder: '请输入一个正整数' })
                            .value(this.inputNumber)
                            .onChange((value: string) => {
                                this.inputNumber = value;
                            })
                            .width('100%')
                            .padding(8)
                            .backgroundColor(Color.White)
                            .borderRadius(4)
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 方法选择
                    Column() {
                        Text('选择算法:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        Select([
                            { value: '暴力枚举法' },
                            { value: '优化枚举法' },
                            { value: '6k±1优化法' },
                            { value: 'Miller-Rabin测试' }
                        ])
                            .value(this.selectedMethod)
                            .onSelect((index: number, value: string) => {
                                this.selectedMethod = value;
                            })
                            .width('100%')
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 结果显示
                    if (this.result) {
                        Column() {
                            Text('检查结果:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.result)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#F5F5F5')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#F5F5F5')
                        .borderRadius(8)
                    }
                    
                    // 所有方法结果显示
                    if (this.allResults) {
                        Column() {
                            Text('所有方法结果:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.allResults)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#E8F5E9')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#E8F5E9')
                        .borderRadius(8)
                    }
                    
                    // 质数列表显示
                    if (this.primeList) {
                        Column() {
                            Text('质数列表:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.primeList)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#FCE4EC')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#FCE4EC')
                        .borderRadius(8)
                    }
                    
                    // 性能数据显示
                    if (this.showPerformance && this.performanceData) {
                        Column() {
                            Text('性能对比:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.performanceData)
                                .fontSize(12)
                                .fontFamily('monospace')
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#FFF3E0')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#FFF3E0')
                        .borderRadius(8)
                    }
                    
                    // 按钮组
                    Row({ space: 12 }) {
                        Button('检查质数')
                            .width('48%')
                            .onClick(() => this.executePrimeCheck())
                            .enabled(!this.isLoading)
                        
                        Button('性能演示')
                            .width('48%')
                            .onClick(() => this.executePerformanceDemo())
                            .enabled(!this.isLoading)
                    }
                    .width('100%')
                    
                    // 加载指示器
                    if (this.isLoading) {
                        LoadingProgress()
                            .width(40)
                            .height(40)
                    }
                }
                .width('100%')
                .padding(16)
            }
            .layoutWeight(1)
        }
        .width('100%')
        .height('100%')
        .backgroundColor('#FAFAFA')
    }
}

ArkTS实现的详细说明

ArkTS版本为OpenHarmony鸿蒙平台提供了完整的用户界面。通过@State装饰器，我们可以管理应用的状态，当用户输入改变时，UI会自动更新。这个实现包含了输入数字的输入框，以及算法选择的下拉菜单。

在计算结果的显示中，我们显示了输入的数字和检查结果。同时，我们还提供了所有方法的结果对比，以及100以内的质数列表，这样用户可以直观地看到质数的分布。

性能演示功能允许用户在应用中直接看到不同算法的性能差异。通过对比10000个数字的检查，用户可以清楚地看到不同实现方式的性能表现。

应用场景分析

1. 密码学应用

在RSA加密算法中，需要生成大质数来构造公钥和私钥。质数检查是密码学系统的基础。

2. 哈希表设计

在设计哈希表时，通常选择质数作为表的大小，以减少哈希碰撞。

3. 随机数生成

在伪随机数生成器中，质数用于构造线性同余生成器等算法。

4. 数据结构优化

在某些数据结构中，质数用于优化性能，例如在Bloom过滤器中。

5. 数学研究

在数论研究中，质数的性质和分布一直是研究的热点。

性能优化建议

1. 选择合适的算法

对于单个数的质数检查，6k±1优化法是最优选择。对于需要找出一定范围内所有质数的场景，埃拉托斯特尼筛法是最优选择。

2. 避免不必要的计算

在检查质数时，可以先检查是否能被2和3整除，这样可以快速排除大部分非质数。

3. 使用缓存

对于需要多次检查相同数字的场景，可以使用缓存来存储已检查的结果。

4. 选择合适的测试方法

对于大数值，Miller-Rabin测试比确定性方法更高效。

总结

质数检查是一个经典的数学问题，虽然问题陈述简单，但其解决方案涉及多种不同的算法思想。从暴力枚举到6k±1优化法，再到Miller-Rabin测试和埃拉托斯特尼筛法，每种方法都有其独特的优势。

通过在KMP框架下实现这个算法，我们可以在多个平台上使用同一套代码，提高开发效率。6k±1优化法是解决单个数质数检查的最优方案，提供了O(√n)的时间复杂度。在OpenHarmony鸿蒙平台上，我们可以通过ArkTS调用Kotlin编译的JavaScript代码，或者直接在ArkTS中实现算法，实现真正的跨平台开发。

掌握这个经典问题的多种解决方案，不仅能够帮助开发者在面试中获得好成绩，更重要的是能够在实际项目中灵活应用这些算法，解决密码学、数据结构优化等实际问题。

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