Numere frumoase

Numerele frumoase sunt numerele care au ca factori primi doar pe 2, 3 si 5. Sirul numerelor frumoase este: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 18, 20, 24, 25 etc.

Fie n un numar natural dat (n<=1500), afisati pe ecran primele n numere frumoase.

n=16

Numere frumoase: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 18, 20, 24, 25 .

• Solutie

Daca analizam problema, putem constata ca orice numar din sir, incepand cu al doilea, se poate obtine inmultind cu 2, 3 sau 5 un numar anterior din sir. Notam cu n2 cel mai mic multiplu de 2 din sir, inca neadaugat, iar cu i indicele din tablou care contine elementul care s-a obtinut prin inmultire cu 2. Vom nota cu n3 cel mai mic multiplu de 3 si indicele j, apoi cu n5 cel mai mic multiplu de 5 si indicele k. Vom adauga numerele pe rand intr-un vector a.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <iostream> using namespace std; int main() { int t=1,n2=2,n3=3,n5=5,i=1,j=1,k=1,l=1,n,a[2000]; cout<<"Dati n: ";cin>>n; a[1]=1; while (l<n) { if (n2<=n3) if (n2<=n5) t=n2; else t=n5; else if (n3<=n5) t=n3; else t=n5; l++; a[l]=t; if (t==n2) n2=2*a[++i]; if (t==n3) n3=3*a[++j]; if (t==n5) n5=5*a[++k]; } for (i=1;i<=l;++i) cout<<a[i]<<" "; return 0; }