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);
    }
}

Bolivian contest problem G – Pares de Ruth-Aaron

Este problema era similar a los de primos, por lo que la Criba de Eratostenes se acomodaba perfectamente.

Explicación:

El 4 tiene como divisor al 2, el 6 también, como se puede apreciar el 2 es divisor de:

2 4 6 8 10 12 ... n*2

el 3 tiene al:

3 6 9 12 ... n*3

pero el 4 no cuenta por que no es primo y por lo tanto no se encuentra en la factorizacion

entonces el 2 debe sumarse a 2, 4, 6, 8, 10 por que se encuentra en la factorizacion de todos sus múltiplos.

Ejemplo de un n = 10:

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 0 0 0 0 0 0 0 0 0   todos empiezan en 0.

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 0 2 0 2 0 2 0 2   (i = 2)
           ^---^---^---^---^    el dos se debe sumar a todos sus múltiplos

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 0 5 0 2 3 2   (i = 3)
             ^-----^-----^    lo mismo con el 3

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 0 5 0 2 3 2   (i = 4)
               ^--------------  no modifica nada por que no es primo se sabe por que ya tiene un valor (2) en su posición.

       0 1 2 3 4 5 6 7 8 9 10
dp[] = 0 0 2 3 2 5 5 0 2 3 7   (i = 5)
                 ^---------^    lo mismo con el 5

       0 1 2 3 4 (5   6) 7 8 9 10
dp[] = 0 0 2 3 2 (5 = 5) 0 2 3 7    ya tenemos el primer par de Ruth-Aaron

Codigo:

vector<int> solve(int n) {
    vector <int> dp(n+1,0);
    for (int i=2;i<n/2;i++) {
        if (!dp[i]) {
            for (int k=i; k<n; k+=i)
                dp[k] += i;
        }
    }
    return dp;
}
int main() {
    vector<int> dp=solve(10000010);
    int a,b;
    while (cin>>a>>b) {
        if (a==0 && b==0)
            break;
        for(int c=a; c<b; c++) {
            if (dp[c]==dp[c+1])
                cout<<c<<" "<<c+1<<endl;
        }
    }
    return 0;
}