El fin estaba algo aburrido y venía de leer el siguiente artículo:
http://tech-queries.blogspot.com/2009/04/amazon-interview.html
Lo conseguí ya que me dio curiosidad como es el Fibonacci con eficiencia (n*log(n)) (http://tech-queries.blogspot.com/2010/09/nth-fibbonacci-number-in-ologn.html)
En eso me dio por hacer un problema en http://www.spoj.pl. Entre en mi cuenta, en la cual tengo como 7 problema hechos y vi cual hacer. Elegí uno de generar números primos( http://www.spoj.pl/problems/PRIME1/). Se da una serie de intervalos y hay que imprimir los números primos que hay en ellos.
Empece a programar en Python y yo ya conocía de la criba de Eratóstenes (http://es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes) para generar números primos. Fui por una solución simple, buscaba el máximo número en el cual un intervalo terminaba y calculaba los primos hasta ahí y luego imprimía los que había en cada uno de los intervalos.
#!/usr/bin/python
# -*- coding: utf-8 -*-
from sys import stdin
def sieve(end):
primes = range(2, end+1)
for i in primes:
j = 2
while i * j <= primes[-1]:
if i * j in primes:
primes.remove(i*j)
j += 1
return primes
if __name__ == "__main__":
end = 0
ncases = int(stdin.readline())
cases = []
for ncase in xrange(ncases):
case = stdin.readline()
case_start, case_end = map(int, case.split(' '))
cases.append({'start' : case_start, 'end' : case_end})
end = max(end, case_end)
primes = sieve(end)
count = 1
for case in cases:
for prime in primes:
if prime < case['start']:
continue
elif prime <= case['end']:
print prime
else:
break
if count != ncases:
print ''
count += 1
No cumplió por problemas de memoria, ya que el arreglo de primos era muy grande, así que decido hacer lo mismo, pero en C++. Me encargue de hacerlo super eficiente en memoria, usando 1 bit por cada primo, en vez de 1 byte. Con mi computadora me tomó unos minutos sacar todos los primos hasta 1000000000. Me generó un archivo de 500 megas.
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;
const char masks [] = {-2, -3, -5, -9, -17, -33, -65, 127};
char *sieve(int max)
{
int max_index = max/8 + 1;
char *primes = new char[max_index];
for(int i = 0; i < max_index; i++)
primes [i] = 255;
for(int i = 2; i <= max; i++)
{
int j = 2;
int mult = 0;
while((mult = i * j) <= max)
{
int index = (mult - 1)/8;
primes[index] &= masks[(mult - 1) % 8];
j++;
}
}
return primes;
}
int main()
{
int ntest;
int case_start, case_end;
int max_end = 0, test = 1;
vector<pair<int, int> > cases;
cin >> ntest;
for(; test <= ntest; test++)
{
cin >> case_start;
cin >> case_end;
pair<int, int> test_case(case_start, case_end);
cases.push_back(test_case);
max_end = (case_end > max_end ? case_end : max_end);
}
char *primes = sieve(max_end);
vector<pair<int, int> >::iterator it;
test = 1;
for ( it=cases.begin() ; it != cases.end(); it++, test++ )
{
pair<int, int> test_case = *it;
case_start = test_case.first;
case_end = test_case.second;
if(!(case_start & 1))
case_start++;
for(case_start; case_start <= case_end; case_start += 2)
{
if(case_start == 1) continue;
int index = (case_start -1)/8;
if(primes[index] & (1 << ((case_start -1) % 8)))
cout << case_start << endl;
}
if(test != ntest)
cout << endl;
}
}
Esta vez se cayó por tiempo. Era claro que no use el modo correcto para calcular las cosas. Pensé un rato y leí un poco por Internet. Resulta que existe una versión segmentada de la criba de Eratóstenes. Se calculan los primos hasta la raíz cuadrada del número (en este caso 32000) y luego con esos primos, se revisa en el intervalo si algo de esos es múltiplo de él, sino es un primo. Lo implemente y por tratar de programar de modo legible, entendible y bonito, se me cayo por tiempo. A la final elimine funciones e hice casi todo en la función principal y lo logre. Perdí un buen tiempo, pero fue interesante.
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define MAX_FIRST_SIEVE_INDEX 32000
#define MAX_FIRST_SIEVE_PRIME 32000
#define MAX_PRIMES 4000
bool sieve[MAX_FIRST_SIEVE_INDEX];
int primes[MAX_PRIMES];
void gen_first()
{
int i = 0, k = 0;
memset(sieve, true, MAX_FIRST_SIEVE_INDEX);
for(i = 2; i <= MAX_FIRST_SIEVE_PRIME; i++)
{
int j = 2;
int mult = 0;
if(sieve[i-1])
primes[k++] = i;
while((mult = i * j) <= MAX_FIRST_SIEVE_PRIME)
{
sieve[mult-1] = false;
j++;
}
}
}
int main()
{
int ntest;
cin >> ntest;
gen_first();
for(int test = 1; test <= ntest; test++)
{
int case_start, case_end;
cin >> case_start;
cin >> case_end;
for(int i = (case_start > 2 ? case_start : 2); i <= case_end; i++)
{
bool print = true;
for(int j = 0; primes[j]*primes[j] <= i; j++)
{
if(i % primes[j] == 0 )
{
print = false;
break;
}
}
if(print) cout << i << endl;
}
if(test != ntest)
cout << endl;
}
}
