Scrieţi un program care citeşte un număr natural
n>1 cu maximum 9 cifre, si afişează valoarea celui
mai mic divizor prim a lui n, precum si puterea la
care acest divizor apare in descompunerea in factori
primi a numărului n.
Răspunsuri la întrebare
Răspuns:
n program care rezolvă această cerință ar putea arăta astfel:
#include <stdio.h>
#include <math.h>
int main()
{
int n;
printf("Introduceti un numar natural n>1 cu maximum 9 cifre: ");
scanf("%d", &n);
int divizor = 2; // cel mai mic divizor prim posibil este 2
int putere = 0; // puterea la care divizorul apare in descompunerea in factori primi a lui n
while (n > 1) // cat timp mai avem cifre in n
{
while (n % divizor == 0) // cat timp numarul n este divizibil cu divizorul curent
{
putere++; // incrementam puterea la care divizorul apare in descompunerea in factori primi a lui n
n /= divizor; // eliminam din n toate aparitiile divizorului curent
}
if (putere > 0) // daca divizorul curent a aparut in descompunerea in factori primi a lui n
{
printf("Cel mai mic divizor prim al lui n este %d si apare la puterea %d\n", divizor, putere);
return 0; // intrucat am gasit cel mai mic divizor prim al lui n, putem termina programul
}
divizor++; // trecem la urmatorul posibil divizor prim
while (divizor <= n / 2 && !isprime(divizor)) // cat timp divizorul curent nu este prim sau este mai mare decat jumatate din n
divizor++; // trecem la urmator
Pentru a continua acest program, putem adăuga implementarea funcției isprime() care verifică dacă un număr este prim sau nu. Aceasta poate arăta astfel:
#include <stdio.h>
#include <math.h>
int isprime(int n)
{
if (n <= 1) // orice numar mai mic sau egal cu 1 nu este prim
return 0;
if (n == 2) // numarul 2 este prim
return 1;
if (n % 2 == 0) // orice numar par mai mare decat 2 nu este prim
return 0;
int i;
for (i = 3; i <= sqrt(n); i += 2) // verificam divizorii impari mai mici decat radical din n
if (n % i == 0) // daca gasim un divizor care imparte n, atunci n nu este prim
return 0;
return 1; // daca nu am gasit niciun divizor care sa imparta n, atunci n este prim
}
int main()
{
int n;
printf("Introduceti un numar natural n>1 cu maximum 9 cifre: ");
scanf("%d", &n);
int divizor = 2; // cel mai mic divizor prim posibil este 2
int putere = 0; // puterea la care divizorul apare in descompunerea in factori primi a lui n
while (n > 1) // cat timp mai avem cifre in n
{
while (n % divizor == 0) // cat timp numarul n este divizibil cu divizorul curent
{
putere++; // incrementam puterea la care divizorul apare in descompunerea in factori primi a lui n
n /= divizor; // eliminam din n toate aparitiile divizorului curent
}
if (putere > 0) // daca divizorul curent a aparut in descompunerea in factori primi a lui n
{
printf("Cel mai mic divizor prim al lui n este %d si apare la puterea %d\n", divizor, putere);
return 0; // intrucat am gasit cel mai mic divizor prim al lui n, putem termina programul
}
Explicație:
Sper să ajute!