•wefgef
|
|
« : Decembrie 23, 2007, 01:33:57 » |
|
Vom folosi un vector phi[], unde phi[ x ] va reprezenta numarul de numere prime cu x, mai mici decat x. Initializam phi[ x ] cu x-1. Apoi parcurgem numerele de la 2 la N, si pentru un numar fixat x, vom scadea din fiecare multiplu de-ai sai phi[ x ]. for (int i = 1; i <= N; ++i) phi[i] = i-1; for (int i = 2; i <= N; ++i) for (int j = 2*i; j <= N; j += i) phi[j] -= phi[i];
Puteti folosi acest cod pentru a rezolva problemele Fractii si Sum. Am decis sa fac un topic separat deoarece este foarte util acest algoritm si apare in multe alte probleme.
|
|
« Ultima modificare: Ianuarie 03, 2008, 16:52:14 de către Andrei Grigorean »
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Dastas
|
|
« Răspunde #1 : Decembrie 23, 2007, 10:21:54 » |
|
Super, eu am facut problema fractii mult mai urat. Tin minte ca generam numere prime si apoi foloseam doua formule. Nu m-am gandit sa fac scazand din multiplii... Mersi mult, foarte folositor!
|
|
« Ultima modificare: Ianuarie 19, 2008, 08:38:06 de către Andrei Grigorean »
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #2 : Decembrie 23, 2007, 11:43:39 » |
|
Merge si asa: for (int i=1;i<=N;i++) phi[i]=i;
for (int i=2;i<=N;i++) if (phi[i]==i) for (j=i;j<=N;j+=i) phi[j] /=i, phi[j] *= (i-1);
In principiu, cred ca ar trebui sa mearga mai repede, pentru se merge mai departe doar din numerele prime. Practic, aici apar inmultiri si impartiri care merg mai incet. Nu stiu daca se face diferenta, dar poate ajuta pe cineva.
|
|
« Ultima modificare: Decembrie 24, 2007, 00:08:15 de către Paul-Dan Baltescu »
|
Memorat
|
Am zis
|
|
|
•bogdan88
Strain
Karma: -3
Deconectat
Mesaje: 32
|
|
« Răspunde #3 : Decembrie 23, 2007, 23:44:41 » |
|
Paul am scris cu ai explicat tu...dar nu da rezultatul corect. poate ai gresit ceva si eu nu imi dau seama
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #4 : Decembrie 24, 2007, 00:08:40 » |
|
Gata, am corectat.
|
|
|
Memorat
|
Am zis
|
|
|
•sandyxp
Strain
Karma: -1
Deconectat
Mesaje: 39
|
|
« Răspunde #5 : Aprilie 03, 2008, 20:36:01 » |
|
0.4 sec pe 1 milion vs 1 sec "ciurul" lui pauldb bate
|
|
|
Memorat
|
|
|
|
•Szabi
Strain
Karma: 1
Deconectat
Mesaje: 2
|
|
« Răspunde #6 : Decembrie 03, 2009, 01:37:19 » |
|
Salut! poate vi se pare o prostie intrebarea mea, dar am o nelamurire... inteleg despre ce e vorba in ciurul lui Erathosthenes si inteleg si indicatorul lui Euler, dar nu inteleg unde se intalnesc cele doua notiuni, adica de unde iese algoritmul descris aici. am folosit deja algoritmul la niste probleme si vad ca functioneaza,dar nu inteleg cum... ma poate lamuri cineva? multumesc anticipat
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #7 : Decembrie 03, 2009, 17:25:00 » |
|
Tu nu folosești efectiv Ciurul, ci doar principiul, adică la început atribui fiecărui număr phi(i) = i-1, 1<=i<=N, iar apoi fac ca la ciur, fiecărui număr ii parcurg toți multipli și scad din phi(j) phi(i), unde j este multiplu al lui i. De ce? Pentru că astfel scad toate numerele care nu sunt relativ prime la j.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #8 : Decembrie 27, 2009, 19:23:04 » |
|
Imi puteti spune exact ce trebuie sa fac dupa ce am calculat phi de fiecare numar? si explicatia pentru care ati facut phi[j]=phi[j]-phi[ i] ? Merci EDIT: M-am prins. Deci de exemplu pentru numarul 6 stim ca are 2 numere prime cu el: si anume 1 si 5. Acum daca numarul N e 7, numarul 6 mai e prim si cu 7. Cum fac mai incolo?Adica nu inteleg de ce fac nr*2+1, unde nr e suma phi-urilor
|
|
« Ultima modificare: Ianuarie 30, 2010, 16:59:20 de către Robert Simoiu »
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #9 : Decembrie 27, 2009, 21:14:26 » |
|
4 nu e prim cu 6. Numerele prime cu 6 mai mici ca el sunt 1 si 5. Iti recomand sa te mai pui la punct cu notiunile matematice elementare (divizibilitate, numar prim, cmmdc, etc.). Nu se poate face informatica fara sa le stapanesti si, din ce am citit scris de tine pe forum, nu e prima ta greseala catastrofala. Presupun ca esti intr-o clasa destul de mica si nu trebuie sa te simti descurajat, de aceea incerc sa te sfatuiesc spre binele tau. Phi(i) = numarul de numere prime cu i mai mici ca i. Tu poti avea i atat la numitor, cat si la numarator, deci de acolo apare 2*phi(i), pentru orice i. Si mai trebuie sa numeri si fractia 1/1.
|
|
|
Memorat
|
Am zis
|
|
|
•SpiderMan
|
|
« Răspunde #10 : Decembrie 27, 2009, 21:16:08 » |
|
4 nu e prim cu 6. Numerele prime cu 6 mai mici ca el sunt 1 si 5. Iti recomand sa te mai pui la punct cu notiunile matematice elementare (divizibilitate, numar prim, cmmdc, etc.). Nu se poate face informatica fara sa le stapanesti si, din ce am citit scris de tine pe forum, nu e prima ta greseala catastrofala. Presupun ca esti intr-o clasa destul de mica si nu trebuie sa te simti descurajat, de aceea incerc sa te sfatuiesc spre binele tau. Phi(i) = numarul de numere prime cu i mai mici ca i. Tu poti avea i atat la numitor, cat si la numarator, deci de acolo apare 2*phi(i), pentru orice i. Si mai trebuie sa numeri si fractia 1/1. Scuze am scris gresit 4 in loc de 1 am fost grabit si am scris gresit scuze, si am inceput informatica de anul asta, clasa a 9-a si merci acum am inteles DE CE era 2* ala ca 1 stiam ca e 1/1 .
|
|
« Ultima modificare: Ianuarie 30, 2010, 16:59:59 de către Robert Simoiu »
|
Memorat
|
|
|
|
•mihai.plesa
Client obisnuit
Karma: 0
Deconectat
Mesaje: 74
|
|
« Răspunde #11 : Aprilie 10, 2011, 07:24:49 » |
|
Merge si asa: for (int i=1;i<=N;i++) phi[i]=i;
for (int i=2;i<=N;i++) if (phi[i]==i) for (j=i;j<=N;j+=i) phi[j] /=i, phi[j] *= (i-1);
In principiu, cred ca ar trebui sa mearga mai repede, pentru se merge mai departe doar din numerele prime. Practic, aici apar inmultiri si impartiri care merg mai incet. Nu stiu daca se face diferenta, dar poate ajuta pe cineva. de ce phi[j] /=i ? de ce phi[j] *=(i-1) ? Multumesc!
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #12 : Aprilie 10, 2011, 11:50:02 » |
|
phi[j] := phi[j] - phi[j]/i = phi[j] * ( 1 - 1/i ) = phi[j] * (i-1)/i Pentru explicatii exista intotdeauna Google
|
|
« Ultima modificare: Aprilie 10, 2011, 12:23:00 de către George Marcus »
|
Memorat
|
|
|
|
•popoiu.george
|
|
« Răspunde #13 : Februarie 24, 2013, 16:59:29 » |
|
Vom folosi un vector phi[], unde phi[ x ] va reprezenta numarul de numere prime cu x, mai mici decat x. Initializam phi[ x ] cu x-1. Apoi parcurgem numerele de la 2 la N, si pentru un numar fixat x, vom scadea din fiecare multiplu de-ai sai phi[ x ].
Cod:
for (int i = 1; i <= N; ++i) phi = i-1; for (int i = 2; i <= N; ++i) for (int j = 2*i; j <= N; j += i) phi[j] -= phi;
Puteti folosi acest cod pentru a rezolva problemele Fractii si Sum.
Am decis sa fac un topic separat deoarece este foarte util acest algoritm si apare in multe alte probleme.
E O(N) ?
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #14 : Februarie 24, 2013, 18:08:31 » |
|
Nu chiar. E O(N log log N).
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #15 : Februarie 25, 2013, 00:39:05 » |
|
E O(nlogn) de fapt.
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #16 : Februarie 25, 2013, 15:15:07 » |
|
Da, scuze. O(N log log N) e pentru Ciurul lui Erastotene, dar acolo se sare peste numerele care nu sunt prime.
|
|
|
Memorat
|
|
|
|
•fdproxy
Strain
Karma: 10
Deconectat
Mesaje: 30
|
|
« Răspunde #17 : Februarie 25, 2013, 18:06:53 » |
|
Pe multe procesoare moderne varianta de mai jos este mai rapida decat varianta originala. // N divizibil cu 4, de exemplu for ( int i = 1; i <= N; i+=4 ) { phi[i] = i - 1; phi[i+1] = i; phi[i+2] = i + 1; phi[i+3] = i + 2; }
// sau
for ( int i = 0; i < N; i+=4 ) { phi[i+1] = i; phi[i+2] = i + 1; phi[i+3] = i + 2; phi[i+4] = i + 3; }
|
|
« Ultima modificare: Februarie 25, 2013, 18:25:59 de către fdproxy »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #18 : Februarie 25, 2013, 18:36:53 » |
|
Din punctul meu de vedere astfel de artificii ar trebui descurajate, cu exceptia catorva ramuri obscure ale industriei.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•emanuel_r
Strain
Karma: 1
Deconectat
Mesaje: 1
|
|
« Răspunde #19 : Septembrie 03, 2016, 19:47:45 » |
|
|
|
|
Memorat
|
|
|
|
|