Sieve of Eratosthenes

This code was tested in problem SPOJ – PRIME1 and some ACM ICPC contests. This considers the prime greater than or equal to 5 have the form: (6^n)+1 or (6^n)-1, for n in the range 1 to ∞.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> primes;
const int MAXP = 31623;
bool criba[MAXP+2];

void generatePrimes() {
    memset(criba, false, sizeof(criba));
    criba[0] = criba[1] = true;
    int raiz = (int) sqrt(MAXP);
    for (int i=3; i<=raiz; i+=2) {
        if (!criba[i])
            for (int j=i*i; j<=MAXP; j += i)
                criba[j] = true;
    }
    primes.push_back(2);
    primes.push_back(3);
    for (int i=5, j=7; i<=MAXP; i+=6, j+=6){
        if (!criba[i])
            primes.push_back(i);
        if (!criba[j])
            primes.push_back(j);
    }
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s