S1死程群群号

s1_prime.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

// Prime[N] = ?
int main(){
    double time_start = clock();
    const int N = 4263116;
    const int UPPER_BOUND = 80000000;
    int *sieve = malloc(UPPER_BOUND * sizeof(int)); 
    
    for (int i = 0; i < UPPER_BOUND; i++){
        sieve[i] = i + 2;
    }

    int prime_count = 0;
    int prime_idx = 0;
    bool done = false;

    while (prime_idx < UPPER_BOUND && prime_count < N){
        while (sieve[prime_idx] == 0){
            prime_idx++;
        }
        prime_count++;
        if (!done){
            int prime = sieve[prime_idx];
            int sieve_iter = prime * prime - 2;
            if (sieve_iter >= UPPER_BOUND)
                done = true;
            else {
                while (sieve_iter < UPPER_BOUND){
                    sieve[sieve_iter] = 0;
                    sieve_iter += prime;
                }
            }
        }
        prime_idx++;
    }
    printf("%d\n", sieve[prime_idx - 1]);
    free(sieve);
    double time_end = clock();
    printf("Used %f seconds\n", (time_end-time_start)/(double)CLOCKS_PER_SEC);
    return 0;
}