本文共 1604 字，大约阅读时间需要 5 分钟。

埃拉托色尼筛法（Sieve of Eratosthenes）是一种高效地找出一定范围内所有素数的算法。在本文中，我们将详细介绍如何使用Objective-C实现这一经典算法。

埃拉托色尼筛法的实现

埃拉托色尼筛法的基本思想是通过逐步筛选来移除非素数，从而找出所有在给定范围内的素数。具体步骤如下：

以下是完整的Objective-C实现代码：

#import 
   
    
NSMutableArray* 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，表示所有数最初都被认为是素数。
• 处理偶数：由于2是最小的素数，直接标记2和所有偶数为非素数。
• 筛选过程：从最小的素数开始，逐个筛选，标记其倍数为非素数。
• 返回结果：最终返回标记数组isPrime，其中YES表示对应的数是素数。

通过这种方法，我们可以高效地找出给定范围内的所有素数。这种方法的时间复杂度为O(n log log n)，在处理较大范围时表现尤为出色。