本文共 1518 字，大约阅读时间需要 5 分钟。
Objective-C实现整数N以内的质数算法
介绍埃拉托斯特尼筛法
埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的算法，用于在一定范围内找出所有的质数。这种方法通过不断筛选非质数，保留质数，最终得到所有小于等于给定整数N的质数。
Objective-C实现代码
#import @interface PrimeNumbers : NSObject- (NSArray *)findPrimesUpToN:(int)N;@end
代码解释
类定义：定义了一个PrimeNumbers类，继承自NSObject。 方法声明：findPrimesUpToN:(int)N方法用于查找小于等于给定整数N的所有质数，并返回一个包含这些质数的数组。 方法实现
@implementation PrimeNumbers- (NSArray *)findPrimesUpToN:(int)N { if (N < 2) { return [NSArray array]; } // 创建一个布尔数组表示每个数是否是质数 BOOL *isPrime = (BOOL *)malloc(N + 1); for (int i = 0; i <= N; i++) { isPrime[i] = true; } isPrime[0] = false; isPrime[1] = false; // 从最小的质数开始筛选 for (int i = 2; i * i <= N; i++) { if (isPrime[i]) { // 标记i的倍数为非质数 for (int j = i * i; j <= N; j += i) { isPrime[j] = false; } } } // 收集所有质数 NSMutableArray *primeNumbers = [NSMutableArray array]; for (int i = 0; i <= N; i++) { if (isPrime[i]) { [primeNumbers addObject:[NSNumber numberWithInt:i]]; } } free(isPrime); return [primeNumbers autorelease];}@end
使用说明
初始化数组：创建一个布尔数组isPrime，用于标记每个数是否为质数。 标记非质数：从最小的质数开始，标记其倍数为非质数。 收集质数：遍历isPrime数组，收集所有为真的值（即质数）。 示例使用
PrimeNumbers *primeFinder = [[PrimeNumbers alloc] init];NSArray *primes = [primeFinder findPrimesUpToN:100];NSLog(@"小于等于100的质数：%@", primes);[primeFinder release];
总结
通过埃拉托斯特尼筛法，我们可以高效地找出小于等于给定整数N的所有质数。上述代码实现了这一算法，适用于需要快速生成质数列表的场景。
转载地址：http://khifk.baihongyu.com/