Question

C++
#1608
Cerința

Se dau n numere naturale nenule. Ordonați descrescător cele n numere după numărul lor de divizori.
Date de intrare

Fișierul de intrare sortare_divizori.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin câte un spațiu.
Date de ieșire

Fișierul de ieșire sortare_divizori.out va conține cele n numere aflate pe a doua linie a fișierului de intrare ordonate descrescător după numărul de divizori.
Restricții și precizări

1 ≤ n ≤ 1000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
dacă există mai multe numere care au același număr de divizori, acestea vor fi ordonate crescător


Exemplu

sortare_divizori.in

5
12 20 4 100 13

sortare_divizori.out

100 12 20 4 13

Explicație

12 are 6 divizori, 20 are 6 divizori, 4 are 3 divizori, 100 are 9 divizori, 13 are 2 divizori, 12 și 20 au același număr de divizori. Așadar ordinea va fi 100 12 20 4 13.

Answer 1

#include <stdio.h> #include <algorithm> using namespace std; FILE *f,*g; struct sir { int nr; int nd; }; sir a[1000]; int n; inline bool cmp(sir a,sir b) { if(a.nd==b.nd) return a.nr<b.nr; else return a.nd>b.nd; } int nrdiv(int n) { int p=1,d,exp=0; // p retine numarul divizorilor if(n%2==0) { while(n%2==0) { exp++; n=n/2; } p*=(exp+1); } d=3; while(n>1) { if(n%d==0) { exp=0; while(n%d==0) { exp++; n=n/d; } p*=(exp+1); } else d+=2; if(n>1&&d*d>n) { p*=2; // aici exp=1 break; } } return p; } int main() { f=fopen("sortare_divizori.in","rt"); g=fopen("sortare_divizori.out","wt"); fscanf(f,"%d",&n); for(int i=0;i<n;i++) { fscanf(f,"%d ",&a[i].nr); a[i].nd=nrdiv(a[i].nr); } sort(a,a+n,cmp); for(int i=0;i<n;i++) fprintf(g,"%d ",a[i].nr); return 0; }