本文共 935 字，大约阅读时间需要 3 分钟。
埃拉托色尼筛法（Sieve of Eratosthenes）是一种高效的算法，用于寻找小于或等于给定数n的所有素数。该算法通过逐步筛选不满足素数条件的数，最终保留所有素数。以下是使用Objective-C实现该算法的详细代码示例。
#importvoid sieveOfEratosthenes(int n) { // 创建一个布尔数组来标记哪些数是素数 BOOL *isPrime = (BOOL*)malloc(n + 1); // 初始化所有数为素数 for (int i = 0; i <= n; i++) { isPrime[i] = true; } // 设置第一个素数2为真 isPrime[0] = false; isPrime[1] = false; // 从最小的素数开始筛选 for (int i = 2; i <= sqrt(n); i++) { if (isPrime[i]) { // 标记i的倍数为非素数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 释放内存 free(isPrime);}
初始化数组：首先，我们创建一个布尔数组isPrime，用于标记每个数是否为素数。数组的长度为n + 1，索引从0到n。
标记非素数：初始时，所有数都被标记为素数。然后，我们将索引0和1标记为非素数，因为它们不是素数。
筛选素数：从最小的素数2开始遍历。如果某个数是素数，那么它的所有倍数都被标记为非素数。
释放内存：在完成筛选后，我们释放isPrime数组的内存，避免内存泄漏。
通过这种方法，我们可以高效地找到小于或等于n的所有素数。该算法的时间复杂度为O(n log log n)，在处理较大数值时表现非常优异。
转载地址：http://cwifk.baihongyu.com/