本文共 1580 字，大约阅读时间需要 5 分钟。
埃拉托色尼筛法（Sieve of Eratosthenes）是一种高效地找出一定范围内所有素数的算法。在本文中，我们将详细介绍如何使用Objective-C实现这一经典算法。
埃拉托色尼筛法的基本思想是通过逐步筛选来移除非素数，从而找出所有在给定范围内的素数。具体步骤如下：
创建布尔数组：首先，我们需要创建一个布尔数组isPrime，用于标记每个数是否为素数。数组的长度为给定的上限limit，初始时所有元素都设置为YES，表示最初假定所有数都是素数。
处理边界条件：由于2是最小的素数，因此我们首先将其标记为素数，并将其后续的偶数全部标记为非素数，以减少计算量。
筛选过程：从最小的素数开始（即从2开始），逐个筛选。对于每一个素数p，我们从p*p开始，到limit结束，步长为p。对于每个位置i，如果isPrime[i]仍为YES，则将其标记为NO，因为它不是素数。
返回结果：最终，数组中所有标记为YES的位置即为所求的素数。
以下是完整的Objective-C实现代码：
#importNSMutableArray* sieveOfEratosthenes(NSInteger limit) { NSMutableArray* isPrime = [[NSMutableArray alloc] init]; // 初始化数组，所有元素初始为YES for (NSInteger i = 0; i <= limit; i++) { [isPrime addObject:[NSNumber numberWithBool:YES]]; } // 处理边界条件：2是最小的素数 if (limit >= 2) { [isPrime replaceObjectAtIndex:1 withObject:[NSNumber numberWithBool:NO]]; // 将所有2的倍数标记为非素数 for (NSInteger i = 4; i <= limit; i += 2) { [isPrime replaceObjectAtIndex:i withObject:[NSNumber numberWithBool:NO]]; } } // 从最小的素数开始筛选 for (NSInteger p = 2; p * p <= limit; p++) { if ([[isPrime objectAtIndex:p] boolValue]) { // 标记p的倍数为非素数 for (NSInteger i = p * p; i <= limit; i += p) { [isPrime replaceObjectAtIndex:i withObject:[NSNumber numberWithBool:NO]]; } } } return isPrime;}
YES的布尔数组isPrime，表示所有数最初都被认为是素数。isPrime，其中YES表示对应的数是素数。通过这种方法，我们可以高效地找出给定范围内的所有素数。这种方法的时间复杂度为O(n log log n)，在处理较大范围时表现尤为出色。
转载地址：http://kvifk.baihongyu.com/