求素数的个数两种解法求解时间分析

本文将详细阐述两种求素数的个数的解法，分别是暴力枚举法和埃氏筛法，并对它们的时间复杂度和应用场景进行分析。

一、暴力枚举法

暴力枚举法是最朴素的解法，从2开始，依次枚举2~n中的每一个数，判断它是否为素数，如果是，素数个数+1。判断某个数是否为素数，可以用它是否能被2~根号n之间的任意一个整数整除来判断。

int countPrimes(int n) {
    int count = 0;
    for(int i = 2; i < n; i++) {
        bool isPrime = true;
        for(int j = 2; j <= sqrt(i); j++) {
            if(i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime)
            count++;
    }
    return count;
}

时间复杂度为O(n*sqrt(n))，空间复杂度为O(1)。显然，暴力枚举法并不适用于大规模的数据。

二、埃氏筛法

埃氏筛法是一种简单而高效的筛法，它通过一个布尔数组来记录每个数字是否为素数，初始时将所有元素设为true，从2开始，依次枚举2~n中的每个数，如果该数为素数，则将它的倍数都标记为非素数。最后，统计布尔数组中true的个数即可。

int countPrimes(int n) {
    bool isPrime[n];
    memset(isPrime, true, sizeof(isPrime));
    int count = 0;
    for(int i = 2; i < n; i++) {
        if(isPrime[i]) {
            count++;
            for(int j = i*i; j < n; j += i)
                isPrime[j] = false;
        }
    }
    return count;
}

时间复杂度为O(n*log(log(n)))，空间复杂度为O(n)。相比于暴力枚举法，埃氏筛法在处理大规模数据时表现更优秀。

三、总结

以上是两种求素数的个数的解法，暴力枚举法适用于小规模数据，时间复杂度较高，在处理大规模数据时会出现超时等问题；而埃氏筛法是一种高效的筛法，其时间复杂度较低，处理大规模数据时表现更加卓越。