质数筛
时间: 2025-04-25 17:35:28 浏览: 18
### 质数筛选算法实现及优化
#### 埃拉托斯特尼筛法简介
埃拉托斯特尼筛法是一种经典的质数筛选算法,能够有效地找出给定范围内的所有质数。此方法通过逐步标记合数来保留质数[^1]。
#### Python 实现埃拉托斯特尼筛法
以下是基于Python语言的埃拉托斯特尼筛法的具体实现:
```python
def prime_sieve(n):
"""Return a list of all primes less than n."""
is_prime = [True] * n
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i*i, n, i):
is_prime[j] = False
return [i for i in range(2, n) if is_prime[i]]
```
上述代码创建了一个布尔数组`is_prime[]`用来记录各个数值是否为质数;遍历过程中一旦发现某个索引对应的值仍保持为真,则将其倍数全部置假表示这些位置上的数字不是质数。
#### 算法性能考量
当处理较大区间时,该算法可能会消耗较多内存资源。因此,在实际应用中可根据具体需求调整数据结构或采用分段策略以降低空间复杂度。此外,还可以考虑其他改进措施如仅保存奇数位等手段进一步提升效率[^3]。
#### Linear Sieve 方法概述
除了传统的埃拉托斯特尼筛法之外,还存在另一种更为高效的线性时间复杂度下的素数筛选方案——Linear Sieve(线性筛),它可以在O(N)时间内完成相同任务并具有更低的空间开销[^4]。
```objc
#import <Foundation/Foundation.h>
@interface LinearSieve : NSObject
+ (NSArray *)sieveOfEratosthenesUpTo:(NSUInteger)n;
@end
@implementation LinearSieve
+ (NSArray *)sieveOfEratosthenesUpTo:(NSUInteger)n {
NSMutableArray *primes = [@[] mutableCopy];
BOOL visited[n+1]; memset(&visited, NO, sizeof(visited));
for (NSUInteger p=2; p<=n; ++p){
if (!visited[p]) [primes addObject:@(p)];
for (NSUInteger q=0;q<[primes count] && p*(NSUInteger)[primes[q] intValue]<=n;++q){
visited[(NSUInteger)p*[primes[q] intValue]] = YES;
if ((NSInteger)p % (NSInteger)[primes[q] intValue]==0) break;
}
}
return primes;
}
@end
```
这段Objective-C代码展示了如何利用线性筛技术快速找到不超过指定上限的所有质数,并且采用了动态规划的思想避免重复计算已知结果从而提高了整体运算速度。
阅读全文
相关推荐

















