02/80 统计素数个数-埃氏筛选法

埃拉托斯特尼筛法（简称埃氏筛）是一种高效的查找素数的算法，它通过排除从2开始到给定数n的所有非素数来找出所有小于或等于n的素数。使用埃氏筛选法改进统计数组中素数元素的个数的算法，我们可以先通过筛法找出数组中所有可能的素数，然后再统计数组中这些素数的个数。

这里是如何用Kotlin实现基于埃氏筛选法来统计一个数组中素数元素的个数：

1. 构建埃氏筛: 根据数组中的最大值构建埃氏筛，以找到所有可能的素数。
2. 统计素数: 遍历数组，利用构建的埃氏筛判断每个元素是否为素数，并计算素数的总数。

fun countPrimesInArrayWithSieve(arr: IntArray): Int {
    if (arr.isEmpty()) return 0

    // 找出数组中的最大值，以便构建足够大的筛
    val max = arr.maxOrNull() ?: 0

    // 构建埃氏筛
    val isPrime = BooleanArray(max + 1) { true }
    isPrime[0] = false
    if (isPrime.size > 1) isPrime[1] = false

    for (i in 2..Math.sqrt(max.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..max step i) {
                isPrime[j] = false
            }
        }
    }

    // 统计数组中的素数个数
    var count = 0
    for (num in arr) {
        if (num >= 2 && isPrime[num]) {
            count++
        }
    }

    return count
}

fun main() {
    val arr = intArrayOf(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
    println("Count of prime numbers in the array with sieve: ${countPrimesInArrayWithSieve(arr)}")
}

在这个实现中，countPrimesInArrayWithSieve 函数首先找出数组中的最大值，以此来确定筛的大小。接着，它通过遍历2到sqrt(max)的数来构建筛，标记所有这些数的倍数为非素数。最后，它遍历数组，统计那些标记为素数的元素个数。

埃氏筛选法的时间复杂度通常为 O(n log log n)，相比暴力法的 O(n^2)，它在处理大量数据时更加高效。