Sieve of Eratosthenese

sieve.cpp

#include <iostream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <random>
#include <omp.h>

#include <stdlib.h>


int main(int argc, char** argv) {
    if (argc < 2) {
        printf("Usage: ./sieve array_size\n");
        return 0;
    }
    int num_trials = 1;
    int n = atoi(argv[1]);
    if (argc > 2) num_trials = atoi(argv[2]);

	bool* B = (bool*)malloc(n*sizeof(bool));

	#pragma omp parallel for
	for(int i = 0;i<(n-1);i+=2){
		//B[i] = i%2==1;
		B[i] = false;
		B[i+1] = true;
	}
	B[n-2] = (n-2)%2==1;
	B[n-1] = (n-1)%2==1;

	//The sieve of Eratosthenes
	//#pragma omp parallel for
	for(size_t i = 2; i < n; ++i) {
		if(!B[i]) continue; //If we are on a composite number, all subsequent numbers have already been handled.

		for(size_t a=2*i; a < n; a+=i ){
			B[a] = false;
		}
	}

	for(size_t i = 2;i<n;++i){
		if(B[i]) std::cout << "" << i << std::endl;
	}

	free(B);



	return 0;
}