本文共 1103 字，大约阅读时间需要 3 分钟。
在 Objective-C 中，埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的算法，可用于生成 n 以内的素数表。这是一种经典的算法，用于找出所有小于或等于给定整数 n 的素数。
以下是一个完整的 Objective-C 示例，展示如何实现该算法并生成素数表。
@interface PrimeGenerator : NSObject
@implementation PrimeGenerator
(NSArray *)generatePrimesUpTo:(int)n {// 初始化一个布尔数组，表示每个数是否为素数bool *isPrime = malloc(n + 1);for (int i = 0; i <= n; i++) {isPrime[i] = true;}isPrime[0] = false;isPrime[1] = false;
// 从最小的素数 2 开始筛选for (int i = 2; i * i <= n; i++) {if (isPrime[i]) {for (int j = i * i; j <= n; j += i) {isPrime[j] = false;}}}
// 收集所有标记为 true 的数NSMutableArray *primes = [NSMutableArray array];for (int i = 2; i <= n; i++) {if (isPrime[i]) {[primes addObject:(id)NSNumber numberWithInt(i)];}}
free(isPrime);return [primes sortedArray];}
(void)printPrimes:(NSArray *)primes {for (NSNumber *num in primes) {NSLog(@"%d", num.intValue);}}
@end
该代码实现了埃拉托斯特尼筛法，通过以下步骤生成 n 以内的素数表：
isPrime，标记每个数是否为素数该算法的时间复杂度为 O(n log log n)，适用于较大的 n 值
转载地址：http://frifk.baihongyu.com/