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

Objective-C实现整数N以内的质数算法

介绍埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的算法，用于在一定范围内找出所有的质数。这种方法通过不断筛选非质数，保留质数，最终得到所有小于等于给定整数N的质数。

Objective-C实现代码

#import 
   
    
@interface PrimeNumbers : NSObject
- (NSArray
    
     *)findPrimesUpToN:(int)N;
@end
    
   

代码解释

方法实现

@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
   

使用说明

示例使用

PrimeNumbers *primeFinder = [[PrimeNumbers alloc] init];
NSArray
   
     *primes = [primeFinder findPrimesUpToN:100];
NSLog(@"小于等于100的质数：%@", primes);
[primeFinder release];
   

总结

通过埃拉托斯特尼筛法，我们可以高效地找出小于等于给定整数N的所有质数。上述代码实现了这一算法，适用于需要快速生成质数列表的场景。