Descompunere în factori primi - metodă rapidă

Salut!

Se citește un număr natural n. Să se afișeze descompunerea în factori primi a lui n.

#include <iostream>
using namespace std;
int n, i, p;
int main(){
cin>>n;
i = 2;
while(n > 1){
	 if(n%i == 0){
		 p = 0;
		 while(n%i == 0){
			 n /= i;
			 p++;
		 }
		 cout<<i<<" "<<p<<"\n";
	 }
	 i++;
}
}

Care ar fi varianta optimizată a acestui algoritm?

https://en.wikipedia...i/Factorization

void PrimeFactors(int n)
{
// Iei separat de cate ori poate fi impartit la 2, imparti la 2 in acelasi timp, daca poate fi impartit

// iei for (int i=3 ; i <= sqrt(n) ; i+=2) si verifici de cate ori poate fi impartit la i; imparti la i daca poate fi impartit

// daca n ramane mai mare ca 2, atunci e prim
if (n > 2)
	 printf("%d %d\n", n, 1);
}

Am niste treaba si stau mai prost cu explicatiile acum.

Edited by sftpdt, 26 November 2014 - 18:56.

Metoda rapida nu exista, altfel nu ar mai exista nimic criptat in informatica.

Nu NIMIC criptat, sint destui algoritmi care nu au treaba cu factorizarea dar da, multa criptografie asimetrica s-ar duce pe apa simbetei.

Oricum algoritmii existenti sint MULT mai rapizi si evoluati decit orice metoda de-asta inventata de mine sau tine.

Eh, nu am intrat in detaliile criptografiei. Am spus ca pentru incepatori

Nu cred că am înțeles cum trebuie ceea ce ai vrut să zici, sftpdt.

#include <iostream>
#include <cmath>
using namespace std;
int n, x, p, b;

int main(){
cin>>n;
x = n;
if(n%2 == 0){
	 while(n%2 == 0){
		 n /= 2;
		 p++;
	 }
	 cout<<2<<" "<<p<<"\n";
}
for(b=3;b<=sqrt(n);b+=2){
	 if(n%b == 0){
		 p = 0;
		 while(n%b == 0){
			 n /= b;
			 p++;
		 }
		 cout<<b<<" "<<p<<"\n";
	 }
}
if(n > 2){
	 cout<<x<<" "<<1;
}
}

De ex. pentru 15 nu afișează corect, problema este la acel "for".

if(n%2 == 0){
		 while(n%2 == 0){
				 n /= 2;
				 p++;
		 }
		 cout<<2<<" "<<p<<"\n";
}

Ai uitat sa initializezi p cu 0.

if(n > 2){
		 cout<<x<<" "<<1;

->

if(n > 2){
		 cout<<n<<" "<<1;

void PrimeFactors(unsigned int number)
{
	unsigned int sum = 0, i;
	while (number % 2 == 0)
	{
		sum++;
		number /= 2;
	}
	if (sum != 0)
	{
		printf("%d^%d\n", 2, sum);
	}
	for (i = 3; i <= sqrt(number); i += 2)
	{
		sum = 0;
		while (number % i == 0)
		{
			sum++;
			number /= i;
		}
		if (sum != 0)
		{
			printf("%d^%d\n", i, sum);
		}
	}
	if (number > 2)
	{
		printf ("%d^%d", number, 1);
	}
}

Edited by sftpdt, 26 November 2014 - 22:53.

Mulțumesc!