要生成从1到小于2^32（即4294967295）的所有质数，由于范围很大（超过40亿个数），直接使用简单的埃拉托斯特尼筛法（Eratosthenes Sieve）会占用过多内存（约4GB），因此需要更高效的算法。推荐使用分段筛法（Segmented Sieve），它通过将整个范围分成较小的段来减少内存使用，同时保持较高的效率。

算法选择：分段埃拉托斯特尼筛法

• 时间复杂度：O(n log log n)，与埃氏筛相同。

• 空间复杂度：O(√n)，即需要存储最大到√n的质数，这里√(2^32) = 2^16 = 65536，因此内存使用约为64KB左右（对于小质数），加上每个段的缓冲区（通常为1MB以下），总内存使用可控。

• 适用性：适用于大范围质数生成，尤其是在32位或64位系统上处理2^32这样的数。

算法步骤

1. 预处理：生成小质数列表（小于等于√n）

   • 计算n = 2^32 - 1 = 4294967295。

   • 计算√n ≈ 65535.9，因此需要生成所有质数 up to 65535。

   • 使用标准的埃氏筛生成这些小质数：

     • 创建一个布尔数组is_prime_small[0..65535]，初始化为true（表示质数）。

     • 标记0和1为false（非质数）。

     • 从2开始，遍历到65535，对于每个质数p，标记所有p的倍数为false。

     • 收集所有true的索引，即为小质数列表small_primes。

2. 分段筛主循环

   • 定义段大小（segment size），例如L = 10^6（1e6），这是一个常见选择，平衡了内存和效率。您可以根据系统缓存调整段大小。

   • 计算总段数：段数 = ceil((n - 1) / L)。注意：范围从2开始，因为1不是质数。

   • 初始化段起始点low = 2，结束点high = min(low + L - 1, n)。

   • 对于每个段：

     • 创建一个布尔数组is_prime_segment[0..L-1]，初始化为true（表示段内数可能为质数）。

     • 对于每个小质数p in small_primes：

       • 计算段内第一个p的倍数：start = ceil(low / p) * p。如果start < p * p，则从p * p开始（因为更小的倍数已被更小的质数标记过）。

       • 如果start大于high，则跳过该p。

       • 否则，从start开始，标记段内所有p的倍数（即索引start - low到high - low，步长为p）为false。

     • 遍历段内每个数：对于索引i从0到L-1，如果is_prime_segment[i]为true，则输出质数low + i。

     • 更新low = low + L，直到low > n。

3. 优化注意事项

   • 整数溢出：由于2^32接近32位整数上限，在计算中使用64位整数（如C++的uint64_t）避免溢出，特别是在计算start = ceil(low / p) * p时。

   • 标记效率：对于小质数p，段内倍数较少时，可以使用循环标记；但对于大p，可能直接跳过。

   • 内存访问：段数组应适合CPU缓存，以提高速度。通常段大小设为1e6到10e6之间，但测试后选择最佳值。

   • 输出处理：质数数量约为n / ln(n) ≈ 2^32 / ln(2^32) ≈ 1.8亿个，直接存储所有质数需要约720MB内存（每个质数4字节）。如果不需要同时存储所有质数，可以逐段输出到文件或流处理。

python版

import math
import time

def sieve_small(limit):
    """生成小于等于limit的所有质数"""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.isqrt(limit)) + 1):
        if is_prime[i]:
            for j in range(i*i, limit+1, i):
                is_prime[j] = False
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

def segmented_sieve(n, output_file="primes.txt"):
    """使用分段筛法找到所有小于等于n的质数并保存到文件"""
    if n < 2:
        return 0
    
    start_time = time.time()
    sqrt_n = int(math.isqrt(n))
    small_primes = sieve_small(sqrt_n)
    
    segment_size = 10**6  # 每个段的大小
    low = 2
    prime_count = 0
    
    # 以写入模式打开文件
    with open(output_file, 'w') as f:
        while low <= n:
            high = min(low + segment_size - 1, n)
            current_segment_size = high - low + 1
            is_prime_seg = [True] * current_segment_size
            
            # 使用小质数标记当前段中的合数
            for p in small_primes:
                # 计算当前段中第一个p的倍数
                start = max(p * p, ((low + p - 1) // p) * p)
                if start > high:
                    continue
                
                start_index = start - low
                # 标记所有p的倍数
                for j in range(start_index, current_segment_size, p):
                    is_prime_seg[j] = False
            
            # 将当前段中的质数写入文件
            for i in range(current_segment_size):
                if is_prime_seg[i]:
                    num = low + i
                    if num <= n:
                        f.write(f"{num}\n")
                        prime_count += 1
            
            # 更新下一个段的起始点
            low += segment_size
            
            # 显示进度（可选）
            if low % (10 * segment_size) == 0 or low > n:
                elapsed = time.time() - start_time
                print(f"处理进度: {min(low, n)}/{n} ({min(100*low//n, 100)}%), "
                      f"已找到质数: {prime_count}, 用时: {elapsed:.2f}秒")
    
    end_time = time.time()
    print(f"完成! 共找到 {prime_count} 个质数，已保存到 {output_file}")
    print(f"总用时: {end_time - start_time:.2f} 秒")
    return prime_count

# 使用示例
if __name__ == "__main__":
    n = 1000005  # 您可以修改这个值，例如 2**32-1
    segmented_sieve(n, "primes.txt")

C++版

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <chrono>
#include <algorithm>
#include <cstdint>

using namespace std;
using namespace std::chrono;

vector<uint32_t> sieve_small(uint32_t limit) {
    if (limit < 2) return {};
    
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    uint32_t sqrt_limit = static_cast<uint32_t>(sqrt(limit));
    for (uint32_t i = 2; i <= sqrt_limit; ++i) {
        if (is_prime[i]) {
            for (uint32_t j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    vector<uint32_t> primes;
    for (uint32_t i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    
    return primes;
}

uint64_t segmented_sieve(uint64_t n, const string& output_file = "primes.txt") {
    if (n < 2) return 0;
    
    auto start_time = high_resolution_clock::now();
    
    uint64_t sqrt_n = static_cast<uint64_t>(sqrt(n));
    vector<uint32_t> small_primes = sieve_small(static_cast<uint32_t>(sqrt_n));
    
    const uint64_t segment_size = 1000000; // 1MB段大小
    uint64_t low = 2;
    uint64_t prime_count = 0;
    
    ofstream outfile(output_file);
    if (!outfile.is_open()) {
        cerr << "无法打开输出文件: " << output_file << endl;
        return 0;
    }
    
    while (low <= n) {
        uint64_t high = min(low + segment_size - 1, n);
        uint64_t current_segment_size = high - low + 1;
        
        vector<bool> is_prime_seg(current_segment_size, true);
        
        for (uint32_t p : small_primes) {
            uint64_t start = max(static_cast<uint64_t>(p) * p, 
                                ((low + p - 1) / p) * p);
            if (start > high) {
                continue;
            }
            
            uint64_t start_index = start - low;
            for (uint64_t j = start_index; j < current_segment_size; j += p) {
                is_prime_seg[j] = false;
            }
        }
        
        // 将质数写入文件
        for (uint64_t i = 0; i < current_segment_size; ++i) {
            if (is_prime_seg[i]) {
                uint64_t num = low + i;
                if (num <= n) {
                    outfile << num << "\n";
                    prime_count++;
                }
            }
        }
        
        low += segment_size;
        
        // 显示进度
        if (low % (10 * segment_size) == 0 || low > n) {
            auto current_time = high_resolution_clock::now();
            auto elapsed = duration_cast<seconds>(current_time - start_time).count();
            double progress = min(100.0 * low / n, 100.0);
            cout << "处理进度: " << min(low, n) << "/" << n 
                 << " (" << progress << "%), "
                 << "已找到质数: " << prime_count
                 << ", 用时: " << elapsed << "秒" << endl;
        }
    }
    
    outfile.close();
    
    auto end_time = high_resolution_clock::now();
    auto total_time = duration_cast<seconds>(end_time - start_time).count();
    
    cout << "完成! 共找到 " << prime_count << " 个质数，已保存到 " << output_file << endl;
    cout << "总用时: " << total_time << " 秒" << endl;
    
    return prime_count;
}

int main() {
    // 测试小范围
    uint64_t n = 1000005;
    // 对于大范围，使用: uint64_t n = 4294967295ULL; // 2^32 - 1
    
    cout << "开始生成小于等于 " << n << " 的所有质数..." << endl;
    
    uint64_t count = segmented_sieve(n, "primes.txt");
    
    if (count > 0) {
        cout << "成功生成 " << count << " 个质数" << endl;
    } else {
        cout << "生成质数失败" << endl;
    }
    
    return 0;
}

优化版本（使用位操作减少内存）

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <chrono>
#include <algorithm>
#include <cstdint>
#include <bitset>

using namespace std;
using namespace std::chrono;

vector<uint32_t> sieve_small(uint32_t limit) {
    if (limit < 2) return {};
    
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    uint32_t sqrt_limit = static_cast<uint32_t>(sqrt(limit));
    for (uint32_t i = 2; i <= sqrt_limit; ++i) {
        if (is_prime[i]) {
            for (uint32_t j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    vector<uint32_t> primes;
    for (uint32_t i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    
    return primes;
}

uint64_t segmented_sieve_optimized(uint64_t n, const string& output_file = "primes_optimized.txt") {
    if (n < 2) return 0;
    
    auto start_time = high_resolution_clock::now();
    
    uint64_t sqrt_n = static_cast<uint64_t>(sqrt(n));
    vector<uint32_t> small_primes = sieve_small(static_cast<uint32_t>(sqrt_n));
    
    const uint64_t segment_size = 1 << 20; // 1MB段大小 (1048576)
    uint64_t low = 2;
    uint64_t prime_count = 0;
    
    ofstream outfile(output_file, ios::binary);
    if (!outfile.is_open()) {
        cerr << "无法打开输出文件: " << output_file << endl;
        return 0;
    }
    
    // 使用位集来减少内存使用
    vector<bool> is_prime_seg(segment_size, true);
    
    while (low <= n) {
        uint64_t high = min(low + segment_size - 1, n);
        
        fill(is_prime_seg.begin(), is_prime_seg.end(), true);
        
        for (uint32_t p : small_primes) {
            uint64_t start = max(static_cast<uint64_t>(p) * p, 
                                ((low + p - 1) / p) * p);
            if (start > high) {
                continue;
            }
            
            uint64_t start_index = start - low;
            for (uint64_t j = start_index; j < segment_size; j += p) {
                is_prime_seg[j] = false;
            }
        }
        
        // 将质数写入文件
        for (uint64_t i = 0; i < segment_size && (low + i) <= n; ++i) {
            if (is_prime_seg[i]) {
                uint64_t num = low + i;
                outfile << num << "\n";
                prime_count++;
            }
        }
        
        low += segment_size;
        
        // 显示进度
        if (low % (10 * segment_size) == 0 || low > n) {
            auto current_time = high_resolution_clock::now();
            auto elapsed = duration_cast<seconds>(current_time - start_time).count();
            double progress = min(100.0 * low / n, 100.0);
            cout << "处理进度: " << min(low, n) << "/" << n 
                 << " (" << progress << "%), "
                 << "已找到质数: " << prime_count
                 << ", 用时: " << elapsed << "秒" << endl;
        }
    }
    
    outfile.close();
    
    auto end_time = high_resolution_clock::now();
    auto total_time = duration_cast<seconds>(end_time - start_time).count();
    
    cout << "完成! 共找到 " << prime_count << " 个质数，已保存到 " << output_file << endl;
    cout << "总用时: " << total_time << " 秒" << endl;
    
    return prime_count;
}

int main() {
    uint64_t n = 1000005;
    // uint64_t n = 4294967295ULL; // 2^32 - 1
    
    cout << "开始生成小于等于 " << n << " 的所有质数..." << endl;
    
    // 使用优化版本
    uint64_t count = segmented_sieve_optimized(n, "primes.txt");
    
    if (count > 0) {
        cout << "成功生成 " << count << " 个质数" << endl;
    } else {
        cout << "生成质数失败" << endl;
    }
    
    return 0;
}