Răspuns:
void generatoare( int n ) {
int a, b;
for ( a = 2; a <= n; a += 2 ) {
b = 1;
while ( a * b + a / b < n )
b ++;
if ( a * b + a / b == n )
cout << a << '-' << b << ' ';
}
}
Explicație:
Complexitate:
Daca luam expresia a * b + a / b si luam doar prima parte, a * b care este mai mica decat expresia noastra, atunci:
pentru un singur a, forul pentru b se va executa de n/a ori, deci complexitatea devine o suma de genul n/2 + n/4 + n/6 + n/8 +... n/n
Dând factor comun pe n/2 suma o sa fie:
n/2( 1 + 1/2 + 1/3 + 1/4 + ... 1/n ), care suma asta este o suma faimoasa si tinde la ln( n ), complexitatea ajungand la n * ln(n) nu n^2
Explicatie program:
primul for, cel pentru 'a' ia fiecare numar posibil pe care il poate lua a
al doilea for, cunoscand 'a', testeaza daca exista un b a.i. expresia sa fie adevarata
Ultimul if testeaza si afiseaza perechea daca expresia este adevarata
