Objective-C实现SieveOfEratosthenes埃拉托色尼筛法打印所有素数算法（附完整源码）-白红宇

Objective-C实现SieveOfEratosthenes埃拉托色尼筛法打印所有素数算法（附完整源码）

阅读量：792 次

发布时间：2023-02-19

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

埃拉托色尼筛法（Sieve of Eratosthenes）是计算机科学中常用的算法之一，用于找出一定范围内的所有素数。作为一名Objective-C开发者，如果你需要实现这一算法来生成小于或等于给定整数的所有素数，那么以下是一个完整的代码实现。

Objective-C实现埃拉托色尼筛法

以下是一个基于Objective-C的埃拉托色尼筛法实现代码示例。这个算法通过创建一个布尔数组来表示每个数字是否为素数，并逐步筛选出所有不为素数的数字。

#import 
   
    @interface SieveOfEratosthenes : NSObject- (void)printPrimesUpTo:(NSInteger)n;@end@implementation SieveOfEratosthenes- (void)printPrimesUpTo:(NSInteger)n {    if (n < 2) {        return;    }        // 创建一个布尔数组来表示每个数是否为素数    NSMutableArray *isPrime = [[NSMutableArray alloc] init];    for (NSInteger i = 2; i <= n; i++) {        [isPrime addObject:@(i)];    }        // 初始化计数器    NSInteger count = 0;        // 从最小的质数开始筛选    for (NSInteger i = 2; i <= n; i++) {        if ([isPrime[i] boolValue]) {            count++;            // 使所有i的倍数变为非素数            for (NSInteger j = i * i; j <= n; j += i) {                [isPrime[j] setObject:@(false) forKey:[NSString stringWithFormat:@"%d", j]];            }        }    }        // 打印所有找到的素数    for (NSInteger i = 2; i <= n; i++) {        if ([isPrime[i] boolValue]) {            NSLog("%d", i);        }    }}@end

算法解释

数组初始化：首先，我们创建一个布尔数组isPrime，其中的每个元素表示对应的数字是否为素数。初始时，所有数字都被认为是素数。

筛选过程：从最小的质数2开始，逐个检查每个数字。如果当前数字是素数（即isPrime[i]为true），那么我们将所有它的倍数标记为非素数。

标记倍数：对于每个质数i，从i*i开始，步长为i，标记所有i的倍数为非素数。

输出结果：最后，遍历isPrime数组，打印所有标记为素数的数字。

代码解释

@interface部分：声明了一个Objective-C类SieveOfEratosthenes，并定义了一个方法printPrimesUpTo:(NSInteger)n，用于生成不大于n的所有素数。

@implementation部分：实现了上述声明的方法。在这个方法中：
- 首先检查输入值是否小于2，如果是，直接返回。
- 创建一个NSMutableArray来存储每个数字是否为素数的信息。
- 从2到n初始化每个数字为素数。
- 初始化计数器count用于统计素数的数量。
- 从2开始遍历每个数字，如果当前数字是素数，则将所有它的倍数标记为非素数。
- 最后遍历isPrime数组，打印所有为真值的数字，即为素数。