本文共 1130 字，大约阅读时间需要 3 分钟。
Objective-C 实现构造 n 以内的素数表
在 Objective-C 中，埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效的算法，可用于生成 n 以内的素数表。这是一种经典的算法，用于找出所有小于或等于给定整数 n 的素数。
以下是一个完整的 Objective-C 示例，展示如何实现该算法并生成素数表。
@interface PrimeGenerator : NSObject
- (NSArray *)generatePrimesUpTo:(int)n;
- (void)printPrimes:(NSArray *)primes; @end
@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 值
发表评论
最新留言
关于作者
