Chirurgia spinală minim invazivă
Chirurgia spinală minim invazivă oferă pacienților oportunitatea unui tratament eficient, permițându-le o recuperare ultra rapidă și nu în ultimul rând minimizând leziunile induse chirurgical. Echipa noastră utilizează un spectru larg de tehnici minim invazive, din care enumerăm câteva: endoscopia cu variantele ei (transnazală, transtoracică, transmusculară, etc), microscopul operator, abordurile trans tubulare și nu în ultimul rând infiltrațiile la toate nivelurile coloanei vertebrale. www.neurohope.ro |
Factori primi
Last Updated: May 20 2017 07:19, Started by
Baggins
, May 19 2017 15:03
·
0
#1
Posted 19 May 2017 - 15:03
Se dă următoarea problemă: https://www.pbinfo.r...robleme&id=1828
Îmi iese din timp pe ultimul test. Pentru a afla redusul unui număr n dat, l-am descompus în factori primi (l-am verificat pe 2, pe 3 și apoi de la 5 am mers cu pasul 6 pentru a reduce timpul) și i-am înmulțit la variabila result. #include <iostream> #include <algorithm> using namespace std; void citire(int* x, int& n) { cin >> n; for (int i = 0; i < n; i++) cin >> x[i]; } void afisare(int* x, int n) { for (int i = 0; i < n; i++) cout << x[i] << ' '; } int redus(int n) { int result = 1; if (n % 2 == 0) { result *= 2; while (n % 2 == 0) n /= 2; } if (n % 3 == 0) { result *= 3; while (n % 3 == 0) n /= 3; } int f = 5; while (n != 1) { if (n % f == 0) { result *= f; while (n % f == 0) n /= f; } if (n % (f + 2) == 0) { result *= (f + 2); while (n % (f + 2) == 0) n /= (f + 2); } f += 6; } return result; } void inlocuire(int* x, int n) { for (int i = 0; i < n; i++) { x[i] = redus(x[i]); } } bool descrescator(int i, int j) { return i > j; } int main() { int x[1005], n; citire(x, n); inlocuire(x, n); sort(x, x + n, descrescator); afisare(x, n); return 0; } |
#2
Posted 19 May 2017 - 15:18
Eu în primul rând nu aș mai împărți n la factorii primi. Nu văd rostul.
Eu unul aș afla cea mai mare valoare din x, un maxX. Aș calcula și salva toate numere prime până la radical din maxX inclusiv. Cel mai probabil în metoda inloc. Și apoi în metoda redus m-aș folosi de numerele prime salvate anterior ca să aflu ce trebuie. Edited by tavitu, 19 May 2017 - 15:25. |
#3
Posted 19 May 2017 - 16:29
Quote În programele C/C++ nu se vor folosi variabile globale. |
#4
Posted 19 May 2017 - 19:09
tavitu, on 19 mai 2017 - 15:18, said:
Aș calcula și salva toate numere prime până la radical din maxX inclusiv. Pe panta asta pe masura ce generezi numerele prime de fapt e bine sa le testezi sa vezi daca sint factori la numerele tale. Oricum o sa faci asta mai incolo dar ai sanse sa scapi calculind numerele prime doar pina la un numar mult mai mic. Deci din calcul pina la radical din max ramii mereu cu calculul pina la radical (max din ce ramine din fiecare numar). In plus o mica optimizare (luam cazul unui singur numar) e ca nu trebuie calculat pina la radical din X ci e suficient de testat daca X e patrat perfect. Daca e am redus problema considerabil (ca avem de cautat factori primi pina la X1/4 cel mult. Daca nu atunci nu avem ce sa mergem mai sus de X1/3 pentru ca oricum nu mai gasim prime la puteri cel putin egale cu 2 in descompunerea lui X. |
#5
Posted 19 May 2017 - 19:33
Quote
Eu unul aș afla cea mai mare valoare din x, un maxX. Aș calcula și salva toate numere prime până la radical din maxX inclusiv. Cel mai probabil în metoda inloc. Și apoi în metoda redus m-aș folosi de numerele prime salvate anterior ca să aflu ce trebuie. Intră 7 7 18 18 5 14 20 4Iese 14 10 7 6 6 5 2Caut maximul din șir => maxX=20 Numerele prime până la sqrt(20), inclusiv, sunt 2 și 3. Ok, și? Cum te folosești de astea? Nu ar trebui să generez nr prime până la maxX, inclusiv? Dacă în exemplu ar fi fost un 23, eu în output trebuie să am un 23 și ca să-l am trebuie să-l salvez. |
#8
Posted 19 May 2017 - 22:04
Quote Nu ar trebui să generez nr prime până la maxX, inclusiv? |
#9
Posted 19 May 2017 - 22:06
nu, până la jumate
până la radical(65) nu l-aș lua și pe 13 |
#10
Posted 19 May 2017 - 22:15
Un număr x are trei cazuri pentru redusul său:
1. dacă x = 1, atunci redusul său este 1 2. dacă x este număr prim redusul său este x 3. dacă x = pk * x2 redusul său este p * redusul lui x2, unde p este un număr prim Ca să demonstrezi că un număr x este prim trebuie să verifici că x nu este divizibil cu nici un număr prim din intervalul [2, radical din x]. Pentru cazul 7 7 18 18 5 14 20 4 Valoarea maximă este 20, sqrt(20) =4,.. , numerele prime în intervalul [2, 4] sunt {2, 3}. Pentru 7 - sqrt(7) = 2,... numere prime în intervalul [2, 2] sunt {2}, 7 nu este divizibil cu nici un număr prim din intervalul respectiv => 7 este număr prim => redusul lui 7 este 7 Pentru 18 - sqrt(18) = 4,... numere prime în intervalul [2, 4] sunt {2, 3}, 18 = 2*9 => redusul lui 18 este 2 * redusul lui 9 = 2 * 3 = 6 Pentru 9 - sqrt(9) = 3, numere prime în intervalul [2, 3] sunt {2, 3}, 9 = 32 * 1 => redusul lui 9 este 3 * redusul lui 1 = 3 * 1 = 3 etc De fiecare dată ai nevoie să calculezi care sunt numerele prime dintr-un interval și apoi să verifici în care caz se încadrează numărul x. Nu are sens să calculezi de fiecare dată numerele prime pentru un număr x, {2, 3, 5, etc}. Tu ai încercat să faci ceva asemenător cu n % f, n% (f + 2) și f += 6, dar asta nu calculează doar numerele prime dintr-un interval ci si numere compuse, care nu de ce să fie verificate, și adaugă timp în mod inutil la durata de execuție. Eu zic că în primă fază ar trebui să vezi cum generezi numerele prime până la inclusiv radical din valoarea maximă. Iar apoi să te gândești la o buclă care testează dacă un număr x este prim sau este pk * x2 folosindu-te de numerele prime și calculeză și redusul în același timp. Și vreau să corectez o afirmație pe care am făcut-o, trebuie să împarți numărul x la factorii primi ca să reduci spațiul de căutare, când am zis că nu are rost am greșit. @f300 Da, am putea testa când le generăm dacă numerele prime sunt factori, dar asta implică ceva subtilități, nu are sens să testăm dacă un număr prim p este un factor prim al unui număr x dacă p > x. Având în vedere că redusul unui număr poate fi definit recursiv am putea folosi o strategie de caching pentru redus și alte optimizări. Edited by tavitu, 19 May 2017 - 22:17. |
|
#11
Posted 19 May 2017 - 22:20
Eu stiu de un singur caz, produs de numere prime distincte
|
#12
Posted 19 May 2017 - 22:25
Depinde cum vrei să privești lucrurile, da, matematic vorbind e un produs de numere prime distincte. Eu am ales să privesc lucrurile într-un mod care ajută la calculat numerele prime respective.
|
#13
Posted 20 May 2017 - 07:19
tavitu, on 19 mai 2017 - 22:15, said:
nu are sens să testăm dacă un număr prim p este un factor prim al unui număr x dacă p > x E mai tare, trebuie testat doar pina la x1/3 in contextul problemei! Este o smecherie, in contextul problemei daca x nu e patrat perfect (lucru care se poate testa simplu) si ai testat toate primele cel mult egale cu x1/3 atunci "redusul" lui x e tot x, nu mai e nevoie sa testezi mai sus. Se poate demonstra usor, daca ai avea inca patrate ce divid x atunci x ar trebui sa fie de forma: x = a2b (1) cu a si b avind factori primi strict mai mari decit x1/3, ceea ce ar inseamna ca a si b sint > x1/3 ceea ce contrazice (1). |
Anunturi
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users