Factorizar un número grande [me refiero a más de 100 dígitos] es complejo, pero para un número hasta 10 ^ 18 tenemos varios algoritmos.
1. División de prueba.
2.Pollard Rho, Brent Pollard Rho, Pollard p-1 … y muchos otros.
- Me dicen que si n = 25, tenemos Sn = 121392 donde Sn es el número de adiciones realizadas en la siguiente función para calcular el enésimo número de Fibonacci. ¿Alguien puede explicar cómo? Int F (int n) {if (n == 0) return (0); if (n == 1) return (1); retorno (F (n-1) + F (n-2));}
- ¿Qué algoritmo debo usar para crear un solucionador de Sudoku?
- ¿Cuáles son algunas de las aplicaciones más elegantes de la teoría de grafos?
- ¿Qué es una función de punto fijo y cuándo son útiles?
- Cómo reducir el problema del camino hamiltoniano al ciclo hamiltoniano (para demostrar que este último es NP-completo)
Llegando a tu pregunta. Para factorizar completamente un número, no necesitamos encontrar todos los números primos menores que iguales al número dado, en realidad solo necesitamos menos que igual a su raíz cuadrada del número. Puede encontrar una explicación en la web por la que solo necesitamos hasta sqrt () del número. A continuación se muestra el código cpp [Implementación de la división de prueba] Ver el código en acción Ideone.com
#include
using namespace std;
#define max 316230
#define ll long long
vectorprimes;
void genPrimes(){
vectorisPrime(max+4,1);
for(int i=2;i*i<=max;i++){
if(isPrime[i]){
for(int j=i;j*i<=max;j++)isPrime[i*j]=0;//marking all nultiple of prime
}
}
primes.push_back(2);
for(int i=3;i<max;i+=2){
if(isPrime[i]){
primes.push_back(i);
}
}
}
map factorNumber(ll n){
map pfact;
for(int i=0;primes[i]*primes[i]<=n;i++){
if(n%primes[i]==0){
while(n%primes[i]==0){
pfact[primes[i]]++;
n/=primes[i];
}
}
}
if(n>1)pfact[n]++;
return pfact;
}
int main() {
ll num;
genPrimes();//genrate all prime till sqrt(10^11)
cin >> num;
map ans = factorNumber(num);
map::iterator it;
for(it=ans.begin();it!=ans.end();it++){
cout<first<<"^"<second<<" ";
}
return 0;
}
