2.统计素数(质数)个数

题目:统计素数个数。

素数:只能被1和自身整除的数,0、1除外

解法一:暴力算法

public class Sushu {
    public static void main(String[] args) {
        System.out.println(countPrimes(100));
    }

    public static int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i) ? 1 : 0;
        }
        return ans;
    }

    /**
     * 是否为素数
     */
    public static boolean isPrime(int x) {
        for (int i = 2; i < x; ++i) {
            //除了1和自身的任意数,取模存在等于0的,则非素数
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

结果:100以内有25个素数

冷知识:for循环第3语句块 ++i 和 i++效果一样,但是 ++i 性能好一些。i++由于是在使用当前值之后再+1,所以需要一个临时的变量来转存。

即使暴力破解,也是有优化空间的。
上面的程序 isPrime ,在 x = 素数时,例11,需要遍历9次( 11%2 11%3 11%4 11%5 11%6 11%7 11%8 11%9 11%10)才能知道这个数字是素数。我们可以利用开根号的方式,减少遍历次数。

//i如果能被x整除,则x/i肯定能被x整除,因此只需判断i和根号x之中较小的即可
    public boolean isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

说明:
11%2 理解为 11/2 = 5 , 11%3 理解为 11/3 = 3,11/4 = 2,之后的 11/5 = 2 其实和最开始的 11/2是没有区别的,所以实际上没有必要再去算 11/5 之后的程序,可以理解为开根号是为了得到临界值

故使用根号推算: 由原来的 i < x 变为 i < √x (也可以使用 Math中的根号方法),此处我们没有用,所以左右一起加平方,即 i * i <= x
 

解法二:埃式筛选法

例 2 * 3,2 * 4 ,肯定等于非素数(合数),所以我们的目标就是省去合数的遍历次数。

public class Sushu {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];
        //初始假定小于n的所有数都为素数
        Arrays.fill(isPrime,true);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return ans;
    }
}

布尔数组初始都为false,为了便于理解,可以用Arrays.fill(booleans,true);将值都改为true

<think>好的,用户想查找使用递归方法统计素数个数算法或代码实现。我需要根据提供的引用资料来回答这个问题。 首先,看看用户提供的引用。引用[2]和[3]都涉及递归判断素数的C语言代码。特别是引用[3]中的代码,里面有一个countPrime函数,用来递归统计数组中的素数个数。这可能对用户有帮助。 用户的问题是如何用递归统计素数个数。递归通常需要分解问题为更小的子问题。比如,检查数组中的每个元素是否是素数,然后递归处理剩余的元素,并将结果累加。 在引用[3]的代码中,countPrime函数就是这样的结构。当n等于1时,检查第一个元素是否为素数;否则,检查当前元素并加上递归处理前n-1个元素的结果。这里使用了埃拉托斯特尼筛法预先生成素数表,提高了效率。 不过,用户可能需要的是直接的递归判断,而不是预先生成素数表的方法。或者,用户可能希望看到如何同时递归判断每个数是否为素数,并统计总数。需要结合递归判断素数和递归遍历数组。 引用[2]中的递归函数f(a,b)用来判断a是否是素数,从b=a-1开始,逐步检查是否能被b整除,直到b=2。如果中间有整除的情况,返回0,否则继续递归。这可能可以整合到统计素数的递归函数中。 所以,可能的解决方案是:编写一个递归函数,遍历数组中的每个元素,对每个元素使用递归方法判断是否为素数,然后累加结果。例如,函数count_primes(arr, n)处理前n个元素,判断第n个元素是否为素数,然后递归调用count_primes(arr, n-1),并将结果相加。 但需要注意,递归遍历数组可能会因为数组长度较大导致栈溢出。但作为示例代码,可以展示这种方法。 需要检查引用中的代码是否符合用户需求。引用[3]的countPrime函数是递归统计,但依赖于预先生成的notprime数组。而用户可能想要的是完全递归的方法,不依赖预处理。 因此,可能需要结合引用[2]中的递归素数判断方法,然后编写一个递归统计函数。例如: 统计函数递归检查数组中的每个元素是否为素数(使用递归判断),然后累加结果。 这样,代码会有两个递归函数:一个用于判断素数,另一个用于统计数组中的素数个数。 需要确保这样的代码示例是正确的,并且能够处理基本情况,比如空数组或单个元素的情况。 另外,用户可能需要解释递归的实现思路,比如分治思想,将问题分解为当前元素的判断和剩余元素的处理。 还需要注意递归的效率问题,比如重复判断同一个数是否为素数可能导致多次递归,效率较低。可以提及优化方法,比如记忆化或者预处理,但用户的问题可能更关注递归实现本身。 最后,根据用户提供的引用,可能需要引用[2]和[3]作为示例,说明不同的递归实现方式。例如,引用[3]中的代码使用预处理筛法加速素数判断,而引用[2]则是纯递归判断素数。 在回答时,应该给出代码示例,并解释递归的工作原理,同时指出可能的效率问题和优化建议。同时,生成相关问题,如递归统计素数的效率如何,如何优化,或者递归与非递归实现的比较等。</think>### 递归统计素数个数的实现思路 要实现递归统计素数个数,通常需要结合**递归遍历数组**和**递归判断素数**两个核心步骤。以下是两种典型实现方式及其代码示例: --- ### 方法一:完全递归实现(不依赖预处理) 此方法直接通过递归函数判断每个数是否为素数,并递归统计总数。代码逻辑分为两部分: 1. **递归素数判断函数**:判断单个数是否为素数 2. **递归统计函数**:遍历数组并累加素数个数 ```c #include <stdio.h> // 递归判断素数,b为当前除数(初始值为n-1) int is_prime(int n, int b) { if (n <= 1) return 0; // 非素数 if (b == 1) return 1; // 无除数能整除,是素数 if (n % b == 0) return 0; // 被整除,非素数 return is_prime(n, b - 1); // 继续检查下一个除数 } // 递归统计数组中的素数个数 int count_primes(int arr[], int n) { if (n == 0) return 0; // 递归终止条件 int current = is_prime(arr[n-1], arr[n-1]-1); return current + count_primes(arr, n-1); // 当前结果 + 剩余元素的结果 } int main() { int arr[] = {2, 3, 4, 5, 6, 7}; int size = sizeof(arr) / sizeof(arr[0]); printf("素数个数:%d\n", count_primes(arr, size)); return 0; } ``` --- ### 方法二:结合预处理优化(效率更高) 通过埃拉托斯特尼筛法预先生成素数表,再递归统计素数个数。此方法牺牲部分空间复杂度以提升时间效率[^3]: ```c #include <stdio.h> int notprime[10001]; // 标记是否为非素数 // 预处理生成素数表(筛法) void init() { notprime[1] = 1; for (int i = 2; i <= 100; i++) { if (!notprime[i]) { for (int j = i * i; j <= 10000; j += i) { notprime[j] = 1; } } } } // 递归统计素数个数 int count_primes(int arr[], int n) { if (n == 0) return 0; return !notprime[arr[n-1]] + count_primes(arr, n-1); // 直接查表判断 } int main() { init(); int arr[] = {2, 3, 4, 5, 6, 7}; int size = sizeof(arr) / sizeof(arr[0]); printf("素数个数:%d\n", count_primes(arr, size)); return 0; } ``` --- ### 关键点解析 1. **递归终止条件**:当数组长度为0时结束递归。 2. **分治思想**:将问题分解为**当前元素判断**和**剩余元素统计**两部分。 3. **效率对比**:完全递归实现的时间复杂度为$O(n \cdot m)$($m$为数值大小),而预处理方法的时间复杂度为$O(n + \sqrt{N})$($N$为数值范围上限),后者更适合大规模数据[^1]。 ---
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值