Question

sortati crescator nr prime dintr un sir, fara modificari (rezolvare simpla in c++)

Answer 1

Program C++

#include <iostream>

using namespace std;

int main(){

int n,v[100],i,j;

bool c[100]={0};

//Citeste datele

cin >> n;

for(i=1;i<=n;i++) cin >> v[i];

//Constuieste vectorul caracteristic in care retinem daca un numar e prim

for(i=1;i<=n;i++){

 if(v[i]<2)c[i]=1;

 for(j=2;j*j<=v[i];j++)

  if(v[i]%j==0)c[i]=1;

}

//Sorteaza valorile prime(v[i] pentru care c[i]=0) - Similar selection sort

for(i=1;i<n;i++){

 if(c[i]==1)continue;

 for(j=i+1;j<=n;j++){

  if(c[j]==1)continue;

  if(v[i]>v[j]){

   int aux=v[i];

   v[i]=v[j];

   v[j]=aux;

  }

 }

}

//Afiseaza vector sortat

for(i=1;i<=n;i++) cout << v[i] << " ";

}

Explicatie :

Programul memoreaza in v sirul de numere citit.

Fiecarui element din v ii corespunde un element din c. Pe fiecare pozitie din c se memoreaza daca elementul corespunzator din v este prim (in acest caz c[i] este egal cu 0) sau daca elementul corespunzator din v nu este prim (in acest caz c[i] este egal cu 1). Vectorul v se numeste vector caracteristic. Folosim aceasta varianta pentru ca altfel am fi nevoiti sa verificam de fiecare data cand comparam daca numerele sunt prime sau nu. Astfel programul este mai simplu si mai eficient.

Folosim o sortare bazata de selection sort pentru ca se pliaza cel mai bine pe problema noastra. Pentru fiecare element v[i] din vector verificam daca acesta este prim. Daca numarul nu e prim (v[i]==1) atunci trecem la elementul v[i+1] urmator (instructiunea continue). Apoi pentru fiecare valoare v[j] care se afla dupa v[i] verificam daca este prima.  Daca numarul nu e prim (v[j]==1) atunci trecem la elementul v[j+1] urmator. Tot ce mai ramane acum de facut e sa comparam v[i] cu v[j] si sa le interschimbam daca este cazul.

In imaginea atasata putem vedea ca sunt modificate doar pozitiile din vector ce contin numere prime si ca numerele prime sunt ordonate crescator. Deci programul functioneaza.

Answer 2

cu functie

#include<iostream>

using namespace std;

int prim(int x){

   if(x<=1)

       return 0;

   for(int d=2;d<=x/2;d++)

       if(x%d==0)

           return 0;

   return 1;

}

int main(){

   int v[101],n;

   cin>>n;

   for(int i=1;i<=n;i++)

       cin>>v[i];

   for(int i=1;i<n;i++)

       for(int j=i+1;j<=n;j++)

           if(prim(v[i])==1&&prim(v[j])==1&&v[i]>v[j])

               swap(v[i],v[j]);

   for(int i=1;i<=n;i++)

       cout<<v[i]<<' ';

   return 0;

}

fara functie

#include<iostream>

using namespace std;

int main(){

   int v[101],n;

   cin>>n;

   for(int i=1;i<=n;i++)

       cin>>v[i];

   for(int i=1;i<n;i++)

       for(int j=i+1;j<=n;j++){

           int k=0,k2=0,max=(v[i]>v[j])?v[i]:v[j];

           for(int d=1;d<=max;d++){

               if(v[i]%d==0) k++;

               if(v[j]%d==0) k2++;

           }

           if(k==2&&k2==2)

               if(v[i]>v[j]){

                   int aux=v[i]; v[i]=v[j]; v[j]=aux;

               }

       }

   for(int i=1;i<=n;i++)

       cout<<v[i]<<' ';

   return 0;

}