Numere Prime Si Divizori

[+skyler_sdf]

Dat un numar prim n<=5000 determinati cel mai mic numar natural care are exact n divizori. Numarul n se va citit de la testatura, iar rezultatele se vor scrie pe ecran, cat si in fisierul "divizori.rez", sub forma specificata in exemplu, adica pe prima linie numarul n si pe urmatoarele linii numarul obtinut

ex: intrare

7

iesire

7

64

ptr ca 64 are 7 divizori(1, 2, 4, 7, 8, 12, 32, 64)

Analiza problemei:

cel mai mic numar care are exact n divizori este 2 la puterea(n-1). Deci va trebui sa scriem un program care sa calculeze puterile lui 2 pentru n mare. Determinarea numarului de cifre al numarului 2 la puterea (n), vom folosi urmatorul principiu

(n*log(2)/log(10))+1

ex: numarul cifrelor lui 2 la puterea(5000) este 1506.

Asadar mai trebuie sa implementam operatia de inmultire a lui 2 cu un numar mare.

#include<iostream.h>

#include<fstream.h>

fstream f;

int inmultire_2(int &k, int *a)

{


	int aux, t=0;

	for(i=0; i<=k; i++)

	{


		aux=t+a[i]*2;

		a[i]=aux%10;

		t=aux/10;


	}

	if(t)

	{


		k++;

		a[k]=t;

		return 1;

	}

}

void write(int k, int *a)

{


	if(k>=0)

	{


		cout<<a[k];

		f<<a[k];

		write(k-1, a);

	}

}

void main()

{


	int a[5000], k=0;

	a[0]=1;

	int n, i;

	f.open("divizori.rez", ios::out);

	cout<<"Dati numarul: ";

	cin>>n;

	f<<n<<"\n";

	for(i=1; i<n; i++)

		inmultire_2(k, a);

	write(k, a);

	f.close();

}