Nu ciurul lui eratostene imi dicteaza mie complexitatea programului. Ciurul lui Eratostene, avand in vedere ca poate sa faca numere pana maxim in 1mil, poate inclusiv sa nu fie luat in calcul. Testat, cu pbinfo, un ciur pana intr-un milion dureaza 0.004 sec =))
Salut Paul! Super tare algoritmul! O intrebare, de ce ai folosit directiva aia pentru "mil"? In principiu am inteles care e treaba cu preprocessor directives, dar nu am inteles cu ce ne ajuta aici.
Hei! In cazul in care ai vrea sa afisezi toate numerele prime mai mici sau egale cu n un algoritm eficient n-ar fi #include using namespace std; int v[10000]; int main() { int n,x=1,i,j; cin>>n; v[1]=3; cout
Algoritmul este ineficient fata de Ciurul lui Eratostene. La tine se verifica FIECARE numar impar daca este divizibil cu vreunul din numerele prime calculate anterior si stocate in vectorul v[i] . Sa faci asta pentru numarul 99.400.891 (9967 x 9973 ambele sunt prime) sa vezi cat iti ia sa descoperi ca nu e prim. Oricum si ciurul din programul al doilea din videoclip poate fi optimizat pentru un castig de executie de cca 5-10%.
@@longOx954 Sigur, complexitatea acestui subprogram este O(n/2), acest lucru inseamnand ca daca ma intereseaza sa aflu daca 1MLD este prim, algoritmul tau ar face 500MIL de pasi, ceea ce nu este bine... Pentru 1 MLD, un algoritm rapid ar trebui sa faca maxim 10.000 de pasi. Cei prezentati de mine fac maxim 7000 de pasi pe verificarea unui numar din preajma numarului 1MLD.
Salut! Esti foarte bun la chestiile astea, ai putea face un video despre algoritmul Miller-Rabin pentru verificarea primalitatii a numerelor?
Poate faci și un video in care explici cum sta treabă cu complexitatea programelor, asta daca nu ai deja
sigur!
Salut , ai putea face un video cum sa configurezi visual studio code pentru c++?
si eu sunt interesat
poti sa ne explici care e diferenta dintre i++ si ++i ?
ua-cam.com/video/U0FlIJx7zAQ/v-deo.html
La aia cu ciuru lu eratostene este log(n) am citit asta pe geeksforgeeks
Nu ciurul lui eratostene imi dicteaza mie complexitatea programului. Ciurul lui Eratostene, avand in vedere ca poate sa faca numere pana maxim in 1mil, poate inclusiv sa nu fie luat in calcul. Testat, cu pbinfo, un ciur pana intr-un milion dureaza 0.004 sec =))
la primul subporgram, numarul 3 mi-l scoate ca fiind ne prim, pentru ca nu intra pe for.
Salut Paul! Super tare algoritmul! O intrebare, de ce ai folosit directiva aia pentru "mil"? In principiu am inteles care e treaba cu preprocessor directives, dar nu am inteles cu ce ne ajuta aici.
Presupun că e o prescurtare pentru “million” sau 1 000 000
11:24 pe 1 ti-l afiseaza ca fiind prim..
if(n == 1 || n == 0)
return false;
mai trebuie pus asta in functie
Hei! In cazul in care ai vrea sa afisezi toate numerele prime mai mici sau egale cu n un algoritm eficient n-ar fi
#include
using namespace std;
int v[10000];
int main()
{
int n,x=1,i,j;
cin>>n;
v[1]=3;
cout
Algoritmul este ineficient fata de Ciurul lui Eratostene. La tine se verifica FIECARE numar impar daca este divizibil cu vreunul din numerele prime calculate anterior si stocate in vectorul v[i] . Sa faci asta pentru numarul 99.400.891 (9967 x 9973 ambele sunt prime) sa vezi cat iti ia sa descoperi ca nu e prim. Oricum si ciurul din programul al doilea din videoclip poate fi optimizat pentru un castig de executie de cca 5-10%.
bool is_prim(int n){
int ost=2;
while(ost
E foarte lent =(
@@ZeceLaExamene poti să-mi spui dece? :))
@@longOx954 Sigur, complexitatea acestui subprogram este O(n/2), acest lucru inseamnand ca daca ma intereseaza sa aflu daca 1MLD este prim, algoritmul tau ar face 500MIL de pasi, ceea ce nu este bine... Pentru 1 MLD, un algoritm rapid ar trebui sa faca maxim 10.000 de pasi. Cei prezentati de mine fac maxim 7000 de pasi pe verificarea unui numar din preajma numarului 1MLD.
@@ZeceLaExamene aaa, am inteles. Mersi pentru raspuns!