Precalcule los números primos usando Tamiz de Eratóstenes. En la tabla de tamizado, el índice numerado primo almacena cero y el índice numerado no primo almacena el factor primo más pequeño del índice.
Podemos lograr esto de la siguiente manera:
//All the elements in sieve tables are intialized to zero
void computeSieve(vector &sieveTable)
{
int sz = sieveTable.size();
for(int i = 2; i*i < sz; i++)
{
if(sieveTable[i] == 0)
{
for(int j = i*i; j < sz; j += i)
{
if(sieveTable[j] == 0) sieveTable[j] = i;
}
}
}
}
Una vez realizada la precomputación, podemos usar la tabla de tamizado para generar resultados en el formato, como se menciona en el problema, de la siguiente manera:
- ¿De qué se trata el algoritmo Google Hawk?
- ¿Qué tecnología utiliza X ?: ¿Cómo implementan las empresas de análisis (Mixpanel, KISSMetrics, etc.) el análisis de embudos?
- ¿Qué es el desaprendizaje en el algoritmo de aprendizaje automático?
- ¿Escribir un programa de CA para convertir un número en palabras de moneda?
- ¿Es posible realizar operaciones de alta frecuencia con la plataforma Zerodha?
//Print prime factors for 'num'
void printFactor(int num, const vector &sieveTable)
{
if(num == 1)
{
cout<<"1\n";
return;
}
else
{
cout<<"1";
while(sieveTable[num] != 0 && num % sieveTable[num] == 0)
{
cout<<" x "<<sieveTable[num];
if(sieveTable[num]==0) break;
num /= sieveTable[num];
}
cout<<" x "<<num<<"\n";
}
}
Aquí está el enlace de la solución completa: Ideone.com
