Question

Probleme cu limita de timp.. ce as putea sa modific ?
Cerinta:
Se dă un vector cu n elemente numere naturale. Să se șteargă din vector toate elementele care sunt numere prime.


#include

using namespace std;

int main()
{
int i,n,prim,d;
cin >> n;
int v[n];
for(i=1; i<=n; i++)
{
cin >> v[i];
prim=1;
for(d=2; d<=v[i]/2; d++)
if(v[i]%d==0)
prim=0;
if(prim==0 || v[i]==1 || v[i]==0)
cout << v[i] << " ";
}
return 0;
}

Answer 1

1) Poti sa stabilesti limita superioara drept radicalul din termen pentru cautarea posibilului divizor maxim. Daca pana la radicalul sau nu gasesti un divizor, inseamna ca nu exista.
Pt 50, tu de exemplu cauti de la 2 la 25. Dar daca pana la 7(radical din 50) nu gasesti vreun divizor, atunci nu ar exista niciunul, pentru ca cei mai mari de 7 trebuie sa fie inmultiti cu unul mai mic decat 7(ex 10*5, 25*2) si ar fi trebuit sa dai de el
2) nu trebuie sa gasesti toti divizorii lui v[i], trebuie sa-l gasesti doar pe primul ca sa stii ca il afisezi. Deci, pui conditia ca pentru impartire exacta la divizor, sa afiseze numarul direct si sa iasa din bucla for ca nu mai are sens sa o faci(cu break)
3) Daca v[i]=0 sau 1, poti sa pui conditia ca este deja de afisat si sa folosesti continue ca sa mergi mai departe in bucla de citire de elemente. Astfel eviti intrarea in for.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
int i,n,prim,d;
cin >> n;
int v[n];
for(i=1; i<=n; i++)
{
cin >> v[i];
if(v[i]==0||v[i]==1){
cout<<v[i]<<" ";
continue;
}
for(d=2; d<=sqrt(v[i]); d++){
if(v[i]%d==0){
cout<<v[i]<<" ";
break;
}
}
}
return 0;
}