Rezolvare completă PbInfo #1307 Siruri1

Cerința

Se citeşte un şir X de numere naturale cu n elemente. Scrieţi un program care determină şirul Y de numere prime distincte, care figurează la puterea întâi în cel puţin o descompunere ȋn factori primi a unui număr din șirul X. Dacă niciun element al şirului X nu are un factor prim la puterea întâi, atunci se va tipări mesajul Sirul Y este vid.

Se vor scrie subprograme pentru:

  • citirea unui şir de numere naturale
  • tipărirea unui şir
  • generarea tuturor numerelor prime mai mici sau egale decât un număr dat SAU verificarea dacă un număr este prim (ȋn funcție de modalitatea de rezolvare aleasă)
  • verificarea dacă un număr figurează la puterea întâi în descompunerea unui număr dat
  • construirea șirului Y

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului X.

Date de ieșire

Programul va afișa pe ecran elementele șirului Y, ordonate crescător, separate prin câte un spațiu.

Restricții și precizări

  • 1 ≤ n ≤ 500
  • cele n numere citite vor fi mai mici decât 1000

Exemplul 1

Intrare

4
77 58 77 31

Ieșire

2 7 11 29 31

Exemplul 2

Intrare

4
64 36 100 125

Ieșire

Sirul Y este vid.

Exemplul 3

Intrare

4
25 5 125 5

Ieșire

5

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Siruri1:

#include <iostream>
using namespace std;

void Citire(int  &, int *);
void Afisare(int , int *);
void Eratostene(int *);
bool Putere1(int , int );
void Construire(int , int * , int & ,int *);

int  v[1001];

int main()
{
    int n,x[501],m,y[1001];
    Citire(n , x);
    Eratostene(v);
    Construire(n , x , m , y);
    if(m > 0)
        Afisare(m , y);
    else
        cout << "Sirul Y este vid.";
    return 0;
}

void Citire(int & n , int * x)
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> x[i];
}

void Afisare(int n , int * x)
{
    for(int i = 1 ; i <= n ; i ++)
        cout << x[i] << " ";
    cout << endl;
}

void Eratostene(int * v)
{
    for(int i = 0 ; i <= 1000 ; i ++)
        v[i] = 1;
    v[0] = v[1] = 0;
    for(int i = 2 ; i * i <= 1000; i ++)
        if(v[i] == 1)
            for(int j = 2 ; i * j <= 1000 ; j ++)
                v[i*j] = 0;
}

bool Putere1(int n , int d)
{
    // returnează true daca d apare la puterea 1 in descompunerea lui n
    int p = 0;
    while(n % d == 0)
        p ++, n /= d;
    return p == 1;
}

void Construire(int n , int * x , int & m, int * y)
{
    m = 0;
    for(int i = 2 ; i <= 1000 ; i ++)
        if(v[i] == 1)
        {
            bool OK = false;
            for(int j = 1 ; j <= n  && ! OK ; j ++)
                if(Putere1(x[j] , i))
                    OK = true;
            if(OK)
                y[++m] = i;
        }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1307 Siruri1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1307 Siruri1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!