Un număr natural nenul se numește p-număr dacă are aceeași paritate cu suma divizorilor săi pozitivi. Exemplu: 10 și 25 sunt p-numere (10 are aceeași paritate cu 18=1+2+5+10, iar 25 are aceeași paritate cu 31=1+5+25). Subprogramul kpn, are trei parametri, a, b și k, prin care primește câte un număr natural din intervalul [1,106] (a≤b). Subprogramul returnează cel de al k-lea p-număr din intervalul [a,b] sau -1, dacă nu există cel puțin k astfel de numere în acest interval. Scrieți definiția completă a subprogramului. Exemplu: dacă a=27, b=50 și k=3, atunci subprogramul returnează 34.
Răspunsuri la întrebare
Răspuns:
int kpn(int a, int b, int k)
{
int i,s;
for(;a<=b&&k!=0;a++)
{
s=1+a;
for(i=2;i<=a/2;i++)
{
if(a%i==0)
{
s+=i;
}
}
if(a%2==s%2)
k--;
}
a--;
if(k==0)return a;
else return -1;
}
Explicație:
Algoritmul parcurge toate numerele de la a pana la b.
for(;a<=b&&k!=0;a++)
Pentru fiecare numar calculeaza suma divizorilor.
for(i=2;i<=a/2;i++)
{
if(a%i==0)
{
s+=i;
}
}
Si mai apoi compara a cu suma, sa verifice daca ambele sunt pare/impare. Daca sunt, scade 1 din k.
if(a%2==s%2)
k--;
Cand k ajunge la 0, structura repetitiva se opreste, iar apoi verifica daca k==0 (for(;a<=b&&k!=0;a++) )(am ajuns la al k-lea numar). daca da returneaza a, daca nu -1, ca in enunt.