本文将详细阐述两种求素数的个数的解法,分别是暴力枚举法和埃氏筛法,并对它们的时间复杂度和应用场景进行分析。
一、暴力枚举法
暴力枚举法是最朴素的解法,从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)。相比于暴力枚举法,埃氏筛法在处理大规模数据时表现更优秀。
三、总结
以上是两种求素数的个数的解法,暴力枚举法适用于小规模数据,时间复杂度较高,在处理大规模数据时会出现超时等问题;而埃氏筛法是一种高效的筛法,其时间复杂度较低,处理大规模数据时表现更加卓越。