Un număr n se numeşte extraprim dacă atât el, cât şi orice număr obţinut prin permutarea cifrelor lui n, sunt numere prime. De exemplu, numărul 113 este un număr extraprim deoarece 113, 311, 131 sunt numere prime.

a) Scrieţi definiţia completă a unui subprogram f, cu un parametru, subprogram care:

- primeşte prin intermediul parametrului a un număr natural cu cel mult 2 cifre (a>1)

- returnează suma exponenţilor divizorilor primi din descompunerea în factori primi a valorii parametrului a.

Exemplu: pentru a=90 subprogramul va returna valoarea 4 (4p.)

b) Scrieţi un program C/C++ care citeşte de la tastatură un număr natural n, 2≤n≤99, şi care determină şi afişează pe ecran, folosind apeluri utile ale subprogramului f, mesajul DA dacă n este un număr extraprim, iar altfel afişează mesajul NU. (6p.)

REZOLVARE

#include<iostream.h>

unsigned n,v[3],p[3],c,extraprim,aux;

unsigned f(unsigned a)

{ unsigned i,nr,s=0;

i=2;

while (i<=a && a!=0)

{ nr=0;

while (a%i==0 && a!=0)

{ a=a/i;

nr++;

}

if (nr!=0) s+=nr;

else i++;

}

return s;

}

void permut(unsigned i)

{ unsigned j,l,nr;

if (i==c)

{nr=0;

for(l=0;l<c;l++)

nr=nr*10+v[p[l]];

if

(f(nr)>1)extraprim=0;

}

else

{ p[i]=i;

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

{ aux=p[i];

p[i]=p[j];

p[j]=aux;

permut(i+1);

aux=p[i];

p[i]=p[j];

p[j]=aux;

}

}

}

void main()

{

do

{

cout<<"n="; cin>>n;

}

while (n<2 || n>99);

unsigned m=n;

c=0;

while (m!=0)

{ v[c]=m%10;

m=m/10;

c++;

}

if (c==2)

{aux=v[0];v[0]=v[1];v[1]=aux;}

extraprim=1;

permut(0);

if (extraprim) cout<<"DA";

else cout<<"NU";

}