divizibilitate.xhtml

        
            
1
            <?xml version="1.0" encoding="UTF-8"?>
        
            
2
            <!DOCTYPE html>
        
            
3
            <html lang="ro" xmlns="http://www.w3.org/1999/xhtml">
        
            
4
                <head>
        
            
5
                    <meta charset="utf-8"/>
        
            
6
                    <title>Algoritmi de divizibilitate</title>
        
            
7
                    <link rel="stylesheet" href="style.css"/>
        
            
8
                </head>
        
            
9
                <body>
        
            
10
                    <h1>Algoritmi de divizibilitate</h1>
        
            
11
                    <section>
        
            
12
                        <h2>Problemă cu sume parțiale</h2>
        
            
13
                        <p>
        
            
14
                            Se dă o matrice de dimensiuni N și M, de numere naturale, și un
        
            
15
                            număr natural K; pentru fiecare celulă să se calculeze latura
        
            
16
                            (impară) minimă a unui pătrat centrat pe celulă astfel încât
        
            
17
                            suma pe acel pătrat să fie cel puțin K. Pătratul trebuie să fie
        
            
18
                            inclus în matrice; dacă nu există niciunul trebuie să se afișeze
        
            
19
                            -1.
        
            
20
                        </p>
        
            
21
                        <h3>Exemplu</h3>
        
            
22
                        <h4>Intrare:</h4>
        
            
23
            <pre>4 6 10
        
            
24
            1 2 3 4 5 6
        
            
25
            36 25 16 9 4 1
        
            
26
            7 7 7 7 7 7
        
            
27
            10 8 10 3 3 3</pre>
        
            
28
                        <h4>Ieșire:</h4>
        
            
29
            <pre>-1 -1 -1 -1 -1 -1
        
            
30
            1 1 1 3 3 -1
        
            
31
            -1 3 3 3 3 -1
        
            
32
            1 -1 1 -1 -1 -1
        
            
33
            </pre>
        
            
34
                    </section>
        
            
35
                    <section>
        
            
36
                        <h2>Aflarea tuturor divizorilor</h2>
        
            
37
                        <p>
        
            
38
                            Funcția următoare calculează lista (neordonată) a divizorilor
        
            
39
                            unui număr. Se folosește de faptul că divizorii sunt în perechi,
        
            
40
                            cu excepția eventualului radical natural al numărului.
        
            
41
                        </p>
        
            
42
            <pre><code>vector&lt;<b>int</b>&gt; divisors(<b>int const</b> x) {
        
            
43
                vector&lt;<b>int</b>&gt; div;
        
            
44
                <b>int</b> d;
        
            
45
                <b>for</b> (d = 1; d*d &lt; x; ++d) {
        
            
46
                    <b>if</b> (!(x % d)) {
        
            
47
                        div.push_back(d);
        
            
48
                        div.push_back(x / d);
        
            
49
                    }
        
            
50
                }
        
            
51
                <b>if</b> (d*d == x) {
        
            
52
                    div.push_back(d);
        
            
53
                }
        
            
54
                <b>return</b> div;
        
            
55
            }</code></pre>
        
            
56
                </section>
        
            
57
                <section>
        
            
58
                    <h2>Aflarea tuturor factorilor primi</h2>
        
            
59
            <pre><code>vector&lt;<b>int</b>&gt; prime_factors(<b>int</b> x) {
        
            
60
                vector&lt;<b>int</b>&gt; pf;
        
            
61
                <b>int</b> d = 2;
        
            
62
                <b>while</b> (d*d &lt;= x &amp;&amp; x != 1) {
        
            
63
                    <b>if</b> (!(x % d)) {
        
            
64
                        pf.push_back(d);
        
            
65
                        <b>do</b> {
        
            
66
                            x /= d;
        
            
67
                        } <b>while</b> (!(x % d));
        
            
68
                    }
        
            
69
                    ++d;
        
            
70
                }
        
            
71
                <b>if</b> (x != 1) {
        
            
72
                    pf.push_back(x);
        
            
73
                }
        
            
74
                <b>return</b> pf;
        
            
75
            }</code></pre>
        
            
76
                    </section>
        
            
77
                    <section>
        
            
78
                        <h2>Cel mai mare divizor comun &#8211; Algoritmul lui Euclid</h2>
        
            
79
            <pre><code><b>int</b> gcd(<b>int</b> a, <b>int</b> b) {
        
            
80
                <b>while</b> (b != 0) {
        
            
81
                    <b>int const</b> r = a % b;
        
            
82
                    a = b;
        
            
83
                    b = r;
        
            
84
                }
        
            
85
                <b>return</b> a;
        
            
86
            }</code></pre>
        
            
87
                    <p>
        
            
88
                        <a href="https://en.wikipedia.org/wiki/File:Euclidean_algorithm_1071_462.gif">
        
            
89
                            Exemplificare vizuală.
        
            
90
                        </a>
        
            
91
                    </p>
        
            
92
                    </section>
        
            
93
                    <section>
        
            
94
                        <h2>Ciurul lui Eratostene</h2>
        
            
95
                        <p>
        
            
96
                            Este un algoritm antic prin care se poate afla, pentru orice număr
        
            
97
                            natural mai mic decât o limită, dacă e număr prim.
        
            
98
                        </p>
        
            
99
                        <p>
        
            
100
                            Se începe cu un vector de N elemente, inițial de valoare 0 (0
        
            
101
                            înseamnă număr prim și 1 înseamnă număr compus). Pozițiile 0 și
        
            
102
                            1 vor avea valoarea 1. Ideea algoritmului este: pentru fiecare element
        
            
103
                            din vector începând cu 2, elementul este prim dacă s-a lucrat
        
            
104
                            la elementele anterioare și încă este nemarcat, deoarece, dacă
        
            
105
                            era compus, ar fi fost marcat anterior. Dacă este prim, se marchează
        
            
106
                            toți multiplii elementului, în afară de el însuși. 
        
            
107
                        </p>
        
            
108
                        <p>
        
            
109
                            Multiplii unui indice <code>i</code> sunt <code>2*i</code>,
        
            
110
                            <code>3*i</code> etc. Deoarece multiplii până la <code>i*i</code>
        
            
111
                            conțin un factor mai mic decât <code>i</code>, nu se mai procesează,
        
            
112
                            fiind deja marcați prin acest factor mai mic.
        
            
113
                        </p>
        
            
114
            <pre><code>vector&lt;<b>char</b>&gt; get_is_prime(<b>int const</b> size) {
        
            
115
                vector&lt;<b>char</b>&gt; sieve(size);
        
            
116
                sieve[0] = 1, sieve[1] = 1;
        
            
117
                <b>for</b> (<b>int</b> i = 2; i*i &lt; size; ++i) {
        
            
118
                    <b>if</b> (!sieve[i]) {
        
            
119
                        <b>for</b> (<b>int</b> j = i*i; j &lt; size; j += i) {
        
            
120
                            sieve[j] = 1;
        
            
121
                        }
        
            
122
                    }
        
            
123
                }
        
            
124
                <b>return</b> sieve;
        
            
125
            }</code></pre>
        
            
126
                    <div class="table-container">
        
            
127
                        <table class="sieve-example">
        
            
128
                            <tr>
        
            
129
                                <td class="sel1">0</td>
        
            
130
                                <td class="sel1">1</td>
        
            
131
                                <td>2</td>
        
            
132
                                <td>3</td>
        
            
133
                                <td>4</td>
        
            
134
                                <td>5</td>
        
            
135
                                <td>6</td>
        
            
136
                                <td>7</td>
        
            
137
                                <td>8</td>
        
            
138
                                <td>9</td>
        
            
139
                                <td>10</td>
        
            
140
                                <td>11</td>
        
            
141
                                <td>12</td>
        
            
142
                                <td>13</td>
        
            
143
                                <td>14</td>
        
            
144
                                <td>15</td>
        
            
145
                            </tr>
        
            
146
                            <tr>
        
            
147
                                <td>16</td>
        
            
148
                                <td>17</td>
        
            
149
                                <td>18</td>
        
            
150
                                <td>19</td>
        
            
151
                                <td>20</td>
        
            
152
                                <td>21</td>
        
            
153
                                <td>22</td>
        
            
154
                                <td>23</td>
        
            
155
                                <td>24</td>
        
            
156
                                <td>25</td>
        
            
157
                                <td>26</td>
        
            
158
                                <td>27</td>
        
            
159
                                <td>28</td>
        
            
160
                                <td>29</td>
        
            
161
                                <td>30</td>
        
            
162
                                <td>31</td>
        
            
163
                            </tr>
        
            
164
                            <tr>
        
            
165
                                <td>32</td>
        
            
166
                                <td>33</td>
        
            
167
                                <td>34</td>
        
            
168
                                <td>35</td>
        
            
169
                                <td>36</td>
        
            
170
                                <td>37</td>
        
            
171
                                <td>38</td>
        
            
172
                                <td>39</td>
        
            
173
                                <td>40</td>
        
            
174
                                <td>41</td>
        
            
175
                                <td>42</td>
        
            
176
                                <td>43</td>
        
            
177
                                <td>44</td>
        
            
178
                                <td>45</td>
        
            
179
                                <td>46</td>
        
            
180
                                <td>47</td>
        
            
181
                            </tr>
        
            
182
                            <tr>
        
            
183
                                <td>48</td>
        
            
184
                                <td>49</td>
        
            
185
                                <td>50</td>
        
            
186
                                <td>51</td>
        
            
187
                                <td>52</td>
        
            
188
                                <td>53</td>
        
            
189
                                <td>54</td>
        
            
190
                                <td>55</td>
        
            
191
                                <td>56</td>
        
            
192
                                <td>57</td>
        
            
193
                                <td>58</td>
        
            
194
                                <td>59</td>
        
            
195
                                <td>60</td>
        
            
196
                                <td>61</td>
        
            
197
                                <td>62</td>
        
            
198
                                <td>63</td>
        
            
199
                            </tr>
        
            
200
                        </table>
        
            
201
                    </div>
        
            
202
                    <div class="table-container">
        
            
203
                        <table class="sieve-example">
        
            
204
                            <tr>
        
            
205
                                <td class="sel1">0</td>
        
            
206
                                <td class="sel1">1</td>
        
            
207
                                <td class="sel4">2</td>
        
            
208
                                <td>3</td>
        
            
209
                                <td class="sel2">4</td>
        
            
210
                                <td>5</td>
        
            
211
                                <td class="sel2">6</td>
        
            
212
                                <td>7</td>
        
            
213
                                <td class="sel2">8</td>
        
            
214
                                <td>9</td>
        
            
215
                                <td class="sel2">10</td>
        
            
216
                                <td>11</td>
        
            
217
                                <td class="sel2">12</td>
        
            
218
                                <td>13</td>
        
            
219
                                <td class="sel2">14</td>
        
            
220
                                <td>15</td>
        
            
221
                            </tr>
        
            
222
                            <tr>
        
            
223
                                <td class="sel2">16</td>
        
            
224
                                <td>17</td>
        
            
225
                                <td class="sel2">18</td>
        
            
226
                                <td>19</td>
        
            
227
                                <td class="sel2">20</td>
        
            
228
                                <td>21</td>
        
            
229
                                <td class="sel2">22</td>
        
            
230
                                <td>23</td>
        
            
231
                                <td class="sel2">24</td>
        
            
232
                                <td>25</td>
        
            
233
                                <td class="sel2">26</td>
        
            
234
                                <td>27</td>
        
            
235
                                <td class="sel2">28</td>
        
            
236
                                <td>29</td>
        
            
237
                                <td class="sel2">30</td>
        
            
238
                                <td>31</td>
        
            
239
                            </tr>
        
            
240
                            <tr>
        
            
241
                                <td class="sel2">32</td>
        
            
242
                                <td>33</td>
        
            
243
                                <td class="sel2">34</td>
        
            
244
                                <td>35</td>
        
            
245
                                <td class="sel2">36</td>
        
            
246
                                <td>37</td>
        
            
247
                                <td class="sel2">38</td>
        
            
248
                                <td>39</td>
        
            
249
                                <td class="sel2">40</td>
        
            
250
                                <td>41</td>
        
            
251
                                <td class="sel2">42</td>
        
            
252
                                <td>43</td>
        
            
253
                                <td class="sel2">44</td>
        
            
254
                                <td>45</td>
        
            
255
                                <td class="sel2">46</td>
        
            
256
                                <td>47</td>
        
            
257
                            </tr>
        
            
258
                            <tr>
        
            
259
                                <td class="sel2">48</td>
        
            
260
                                <td>49</td>
        
            
261
                                <td class="sel2">50</td>
        
            
262
                                <td>51</td>
        
            
263
                                <td class="sel2">52</td>
        
            
264
                                <td>53</td>
        
            
265
                                <td class="sel2">54</td>
        
            
266
                                <td>55</td>
        
            
267
                                <td class="sel2">56</td>
        
            
268
                                <td>57</td>
        
            
269
                                <td class="sel2">58</td>
        
            
270
                                <td>59</td>
        
            
271
                                <td class="sel2">60</td>
        
            
272
                                <td>61</td>
        
            
273
                                <td class="sel2">62</td>
        
            
274
                                <td>63</td>
        
            
275
                            </tr>
        
            
276
                        </table>
        
            
277
                    </div>
        
            
278
                    <div class="table-container">
        
            
279
                        <table class="sieve-example">
        
            
280
                            <tr>
        
            
281
                                <td class="sel1">0</td>
        
            
282
                                <td class="sel1">1</td>
        
            
283
                                <td class="sel3">2</td>
        
            
284
                                <td class="sel4">3</td>
        
            
285
                                <td class="sel1">4</td>
        
            
286
                                <td>5</td>
        
            
287
                                <td class="sel1">6</td>
        
            
288
                                <td>7</td>
        
            
289
                                <td class="sel1">8</td>
        
            
290
                                <td class="sel2">9</td>
        
            
291
                                <td class="sel1">10</td>
        
            
292
                                <td>11</td>
        
            
293
                                <td class="sel2">12</td>
        
            
294
                                <td>13</td>
        
            
295
                                <td class="sel1">14</td>
        
            
296
                                <td class="sel2">15</td>
        
            
297
                            </tr>
        
            
298
                            <tr>
        
            
299
                                <td class="sel1">16</td>
        
            
300
                                <td>17</td>
        
            
301
                                <td class="sel2">18</td>
        
            
302
                                <td>19</td>
        
            
303
                                <td class="sel1">20</td>
        
            
304
                                <td class="sel2">21</td>
        
            
305
                                <td class="sel1">22</td>
        
            
306
                                <td>23</td>
        
            
307
                                <td class="sel2">24</td>
        
            
308
                                <td>25</td>
        
            
309
                                <td class="sel1">26</td>
        
            
310
                                <td class="sel2">27</td>
        
            
311
                                <td class="sel1">28</td>
        
            
312
                                <td>29</td>
        
            
313
                                <td class="sel2">30</td>
        
            
314
                                <td>31</td>
        
            
315
                            </tr>
        
            
316
                            <tr>
        
            
317
                                <td class="sel1">32</td>
        
            
318
                                <td class="sel2">33</td>
        
            
319
                                <td class="sel1">34</td>
        
            
320
                                <td>35</td>
        
            
321
                                <td class="sel2">36</td>
        
            
322
                                <td>37</td>
        
            
323
                                <td class="sel1">38</td>
        
            
324
                                <td class="sel2">39</td>
        
            
325
                                <td class="sel1">40</td>
        
            
326
                                <td>41</td>
        
            
327
                                <td class="sel2">42</td>
        
            
328
                                <td>43</td>
        
            
329
                                <td class="sel1">44</td>
        
            
330
                                <td class="sel2">45</td>
        
            
331
                                <td class="sel1">46</td>
        
            
332
                                <td>47</td>
        
            
333
                            </tr>
        
            
334
                            <tr>
        
            
335
                                <td class="sel2">48</td>
        
            
336
                                <td>49</td>
        
            
337
                                <td class="sel1">50</td>
        
            
338
                                <td class="sel2">51</td>
        
            
339
                                <td class="sel1">52</td>
        
            
340
                                <td>53</td>
        
            
341
                                <td class="sel2">54</td>
        
            
342
                                <td>55</td>
        
            
343
                                <td class="sel1">56</td>
        
            
344
                                <td class="sel2">57</td>
        
            
345
                                <td class="sel1">58</td>
        
            
346
                                <td>59</td>
        
            
347
                                <td class="sel2">60</td>
        
            
348
                                <td>61</td>
        
            
349
                                <td class="sel1">62</td>
        
            
350
                                <td class="sel2">63</td>
        
            
351
                            </tr>
        
            
352
                        </table>
        
            
353
                    </div>
        
            
354
                    <div class="table-container">
        
            
355
                        <table class="sieve-example">
        
            
356
                            <tr>
        
            
357
                                <td class="sel1">0</td>
        
            
358
                                <td class="sel1">1</td>
        
            
359
                                <td class="sel3">2</td>
        
            
360
                                <td class="sel3">3</td>
        
            
361
                                <td class="sel1">4</td>
        
            
362
                                <td class="sel4">5</td>
        
            
363
                                <td class="sel1">6</td>
        
            
364
                                <td>7</td>
        
            
365
                                <td class="sel1">8</td>
        
            
366
                                <td class="sel1">9</td>
        
            
367
                                <td class="sel1">10</td>
        
            
368
                                <td>11</td>
        
            
369
                                <td class="sel1">12</td>
        
            
370
                                <td>13</td>
        
            
371
                                <td class="sel1">14</td>
        
            
372
                                <td class="sel1">15</td>
        
            
373
                            </tr>
        
            
374
                            <tr>
        
            
375
                                <td class="sel1">16</td>
        
            
376
                                <td>17</td>
        
            
377
                                <td class="sel1">18</td>
        
            
378
                                <td>19</td>
        
            
379
                                <td class="sel1">20</td>
        
            
380
                                <td class="sel1">21</td>
        
            
381
                                <td class="sel1">22</td>
        
            
382
                                <td>23</td>
        
            
383
                                <td class="sel1">24</td>
        
            
384
                                <td class="sel2">25</td>
        
            
385
                                <td class="sel1">26</td>
        
            
386
                                <td class="sel1">27</td>
        
            
387
                                <td class="sel1">28</td>
        
            
388
                                <td>29</td>
        
            
389
                                <td class="sel2">30</td>
        
            
390
                                <td>31</td>
        
            
391
                            </tr>
        
            
392
                            <tr>
        
            
393
                                <td class="sel1">32</td>
        
            
394
                                <td class="sel1">33</td>
        
            
395
                                <td class="sel1">34</td>
        
            
396
                                <td class="sel2">35</td>
        
            
397
                                <td class="sel1">36</td>
        
            
398
                                <td>37</td>
        
            
399
                                <td class="sel1">38</td>
        
            
400
                                <td class="sel1">39</td>
        
            
401
                                <td class="sel2">40</td>
        
            
402
                                <td>41</td>
        
            
403
                                <td class="sel1">42</td>
        
            
404
                                <td>43</td>
        
            
405
                                <td class="sel1">44</td>
        
            
406
                                <td class="sel2">45</td>
        
            
407
                                <td class="sel1">46</td>
        
            
408
                                <td>47</td>
        
            
409
                            </tr>
        
            
410
                            <tr>
        
            
411
                                <td class="sel1">48</td>
        
            
412
                                <td>49</td>
        
            
413
                                <td class="sel2">50</td>
        
            
414
                                <td class="sel1">51</td>
        
            
415
                                <td class="sel1">52</td>
        
            
416
                                <td>53</td>
        
            
417
                                <td class="sel1">54</td>
        
            
418
                                <td class="sel2">55</td>
        
            
419
                                <td class="sel1">56</td>
        
            
420
                                <td class="sel1">57</td>
        
            
421
                                <td class="sel1">58</td>
        
            
422
                                <td>59</td>
        
            
423
                                <td class="sel2">60</td>
        
            
424
                                <td>61</td>
        
            
425
                                <td class="sel1">62</td>
        
            
426
                                <td class="sel1">63</td>
        
            
427
                            </tr>
        
            
428
                        </table>
        
            
429
                    </div>
        
            
430
                    <div class="table-container">
        
            
431
                        <table class="sieve-example">
        
            
432
                            <tr>
        
            
433
                                <td class="sel1">0</td>
        
            
434
                                <td class="sel1">1</td>
        
            
435
                                <td class="sel3">2</td>
        
            
436
                                <td class="sel3">3</td>
        
            
437
                                <td class="sel1">4</td>
        
            
438
                                <td class="sel3">5</td>
        
            
439
                                <td class="sel1">6</td>
        
            
440
                                <td class="sel4">7</td>
        
            
441
                                <td class="sel1">8</td>
        
            
442
                                <td class="sel1">9</td>
        
            
443
                                <td class="sel1">10</td>
        
            
444
                                <td>11</td>
        
            
445
                                <td class="sel1">12</td>
        
            
446
                                <td>13</td>
        
            
447
                                <td class="sel1">14</td>
        
            
448
                                <td class="sel1">15</td>
        
            
449
                            </tr>
        
            
450
                            <tr>
        
            
451
                                <td class="sel1">16</td>
        
            
452
                                <td>17</td>
        
            
453
                                <td class="sel1">18</td>
        
            
454
                                <td>19</td>
        
            
455
                                <td class="sel1">20</td>
        
            
456
                                <td class="sel1">21</td>
        
            
457
                                <td class="sel1">22</td>
        
            
458
                                <td>23</td>
        
            
459
                                <td class="sel1">24</td>
        
            
460
                                <td class="sel1">25</td>
        
            
461
                                <td class="sel1">26</td>
        
            
462
                                <td class="sel1">27</td>
        
            
463
                                <td class="sel1">28</td>
        
            
464
                                <td>29</td>
        
            
465
                                <td class="sel1">30</td>
        
            
466
                                <td>31</td>
        
            
467
                            </tr>
        
            
468
                            <tr>
        
            
469
                                <td class="sel1">32</td>
        
            
470
                                <td class="sel1">33</td>
        
            
471
                                <td class="sel1">34</td>
        
            
472
                                <td class="sel1">35</td>
        
            
473
                                <td class="sel1">36</td>
        
            
474
                                <td>37</td>
        
            
475
                                <td class="sel1">38</td>
        
            
476
                                <td class="sel1">39</td>
        
            
477
                                <td class="sel1">40</td>
        
            
478
                                <td>41</td>
        
            
479
                                <td class="sel1">42</td>
        
            
480
                                <td>43</td>
        
            
481
                                <td class="sel1">44</td>
        
            
482
                                <td class="sel1">45</td>
        
            
483
                                <td class="sel1">46</td>
        
            
484
                                <td>47</td>
        
            
485
                            </tr>
        
            
486
                            <tr>
        
            
487
                                <td class="sel1">48</td>
        
            
488
                                <td class="sel2">49</td>
        
            
489
                                <td class="sel1">50</td>
        
            
490
                                <td class="sel1">51</td>
        
            
491
                                <td class="sel1">52</td>
        
            
492
                                <td>53</td>
        
            
493
                                <td class="sel1">54</td>
        
            
494
                                <td class="sel1">55</td>
        
            
495
                                <td class="sel2">56</td>
        
            
496
                                <td class="sel1">57</td>
        
            
497
                                <td class="sel1">58</td>
        
            
498
                                <td>59</td>
        
            
499
                                <td class="sel1">60</td>
        
            
500
                                <td>61</td>
        
            
501
                                <td class="sel1">62</td>
        
            
502
                                <td class="sel2">63</td>
        
            
503
                            </tr>
        
            
504
                        </table>
        
            
505
                    </div>
        
            
506
                    <div class="table-container">
        
            
507
                        <table class="sieve-example">
        
            
508
                            <tr>
        
            
509
                                <td class="sel1">0</td>
        
            
510
                                <td class="sel1">1</td>
        
            
511
                                <td class="sel3">2</td>
        
            
512
                                <td class="sel3">3</td>
        
            
513
                                <td class="sel1">4</td>
        
            
514
                                <td class="sel3">5</td>
        
            
515
                                <td class="sel1">6</td>
        
            
516
                                <td class="sel3">7</td>
        
            
517
                                <td class="sel1">8</td>
        
            
518
                                <td class="sel1">9</td>
        
            
519
                                <td class="sel1">10</td>
        
            
520
                                <td class="sel3">11</td>
        
            
521
                                <td class="sel1">12</td>
        
            
522
                                <td class="sel3">13</td>
        
            
523
                                <td class="sel1">14</td>
        
            
524
                                <td class="sel1">15</td>
        
            
525
                            </tr>
        
            
526
                            <tr>
        
            
527
                                <td class="sel1">16</td>
        
            
528
                                <td class="sel3">17</td>
        
            
529
                                <td class="sel1">18</td>
        
            
530
                                <td class="sel3">19</td>
        
            
531
                                <td class="sel1">20</td>
        
            
532
                                <td class="sel1">21</td>
        
            
533
                                <td class="sel1">22</td>
        
            
534
                                <td class="sel3">23</td>
        
            
535
                                <td class="sel1">24</td>
        
            
536
                                <td class="sel1">25</td>
        
            
537
                                <td class="sel1">26</td>
        
            
538
                                <td class="sel1">27</td>
        
            
539
                                <td class="sel1">28</td>
        
            
540
                                <td class="sel3">29</td>
        
            
541
                                <td class="sel1">30</td>
        
            
542
                                <td class="sel3">31</td>
        
            
543
                            </tr>
        
            
544
                            <tr>
        
            
545
                                <td class="sel1">32</td>
        
            
546
                                <td class="sel1">33</td>
        
            
547
                                <td class="sel1">34</td>
        
            
548
                                <td class="sel1">35</td>
        
            
549
                                <td class="sel1">36</td>
        
            
550
                                <td class="sel3">37</td>
        
            
551
                                <td class="sel1">38</td>
        
            
552
                                <td class="sel1">39</td>
        
            
553
                                <td class="sel1">40</td>
        
            
554
                                <td class="sel3">41</td>
        
            
555
                                <td class="sel1">42</td>
        
            
556
                                <td class="sel3">43</td>
        
            
557
                                <td class="sel1">44</td>
        
            
558
                                <td class="sel1">45</td>
        
            
559
                                <td class="sel1">46</td>
        
            
560
                                <td class="sel3">47</td>
        
            
561
                            </tr>
        
            
562
                            <tr>
        
            
563
                                <td class="sel1">48</td>
        
            
564
                                <td class="sel1">49</td>
        
            
565
                                <td class="sel1">50</td>
        
            
566
                                <td class="sel1">51</td>
        
            
567
                                <td class="sel1">52</td>
        
            
568
                                <td class="sel3">53</td>
        
            
569
                                <td class="sel1">54</td>
        
            
570
                                <td class="sel1">55</td>
        
            
571
                                <td class="sel1">56</td>
        
            
572
                                <td class="sel1">57</td>
        
            
573
                                <td class="sel1">58</td>
        
            
574
                                <td class="sel3">59</td>
        
            
575
                                <td class="sel1">60</td>
        
            
576
                                <td class="sel3">61</td>
        
            
577
                                <td class="sel1">62</td>
        
            
578
                                <td class="sel1">63</td>
        
            
579
                            </tr>
        
            
580
                        </table>
        
            
581
                    </div>
        
            
582
                    </section>
        
            
583
                    <section>
        
            
584
                        <h2>Algoritmi asemănători cu Ciurul lui Eratostene</h2>
        
            
585
                        <p>
        
            
586
                            Atenție de la ce multiplu începem să parcurgem vectorul.
        
            
587
                            Dacă trebuie să numărăm toți factorii primi, parcurgem
        
            
588
                            începând de la <code>i</code>, nu de la <code>i*i</code>.
        
            
589
                            De asemenea, unii algoritmi cer să realizăm parcurgerea
        
            
590
                            multiplilor tuturor numerelor, nu doar a celor prime,
        
            
591
                            în cazul în care vrem să numărăm, de exemplu, toți
        
            
592
                            divizorii.
        
            
593
                        </p>
        
            
594
            
        
            
595
                        <p>
        
            
596
                            <b>Observații:</b>
        
            
597
                        </p>
        
            
598
                        <ul>
        
            
599
                            <li>
        
            
600
                                Pentru orice număr sub 2310 sunt maxim 4 factori primi.
        
            
601
                            </li>
        
            
602
                            <li>
        
            
603
                                Pentru orice număr sub 30030 sunt maxim 5 factori primi.
        
            
604
                            </li>
        
            
605
                            <li>
        
            
606
                                Pentru orice număr sub 510510 sunt maxim 6 factori primi.
        
            
607
                            </li>
        
            
608
                            <li>
        
            
609
                                Pentru orice număr sub 9699690 sunt maxim 7 factori primi.
        
            
610
                            </li>
        
            
611
                            <li>
        
            
612
                                15 factori primi sunt suficienți pentru orice număr natural
        
            
613
                                de până la 2<sup>64</sup>. Nu putem însă face vreun ciur
        
            
614
                                de această dimensiune, deoarece nu există calculator cu
        
            
615
                                atâta memorie.
        
            
616
                            </li>
        
            
617
                            <li>
        
            
618
                                Numerele prime au un singur factor prim, adică numărul însuși.
        
            
619
                            </li>
        
            
620
                        </ul>
        
            
621
                        <h3>Numărul de factori primi</h3>
        
            
622
                        <p>
        
            
623
                            De exemplu, 42 are factorii primi 2, 3 și 7.
        
            
624
                        </p>
        
            
625
            <pre><code>vector&lt;<b>char</b>&gt; get_pf_count(<b>int const</b> size) {
        
            
626
                vector&lt;<b>char</b>&gt; sieve(size);
        
            
627
                sieve[0] = -1, sieve[1] = 0;
        
            
628
                <b>for</b> (<b>int</b> i = 2; i &lt; size; ++i) {
        
            
629
                    <b>if</b> (!sieve[i]) {
        
            
630
                        <b>for</b> (<b>int</b> j = i; j &lt; size; j += i) {
        
            
631
                            ++sieve[j];
        
            
632
                        }
        
            
633
                    }
        
            
634
                }
        
            
635
                <b>return</b> sieve;
        
            
636
            }</code></pre>
        
            
637
                        <p>
        
            
638
                            Deoarece pentru orice număr care încape în dimensiunea
        
            
639
                            memoriei sunt mult sub 256 de factori primi, tipul
        
            
640
                            <code><b>char</b></code> ar trebui să fie suficient
        
            
641
                            pentru acest calcul.
        
            
642
                        </p>
        
            
643
                        <h3>Suma divizorilor</h3>
        
            
644
            <pre><code>vector&lt;<b>int</b>&gt; get_divisor_sum(<b>int const</b> size) {
        
            
645
                vector&lt;<b>int</b>&gt; sieve(size);
        
            
646
                sieve[0] = -1;
        
            
647
                <b>for</b> (<b>int</b> i = 1; i &lt; size; ++i) {
        
            
648
                    <b>for</b> (<b>int</b> j = i; j &lt; size; j += i) {
        
            
649
                        sieve[j] += i;
        
            
650
                    }
        
            
651
                }
        
            
652
                <b>return</b> sieve;
        
            
653
            }</code></pre>
        
            
654
                        <h3>Cel mai mare/cel mai mic factor prim</h3>
        
            
655
            <pre><code>vector&lt;<b>int</b>&gt; get_max_pf(<b>int const</b> size) {
        
            
656
                vector&lt;<b>int</b>&gt; sieve(size);
        
            
657
                sieve[0] = -1, sieve[1] = -1;
        
            
658
                <b>for</b> (<b>int</b> i = 2; i &lt; size; ++i) {
        
            
659
                    <b>if</b> (!sieve[i]) {
        
            
660
                        <b>for</b> (<b>int</b> j = i; j &lt; size; j += i) {
        
            
661
                            sieve[j] = i;
        
            
662
                        }
        
            
663
                    }
        
            
664
                }
        
            
665
                <b>return</b> sieve;
        
            
666
            }</code></pre>
        
            
667
            <pre><code>vector&lt;<b>int</b>&gt; get_min_pf(<b>int const</b> size) {
        
            
668
                vector&lt;<b>int</b>&gt; sieve(size);
        
            
669
                sieve[0] = -1, sieve[1] = -1;
        
            
670
                <b>for</b> (<b>int</b> i = 2; i &lt; size; ++i) {
        
            
671
                    <b>if</b> (!sieve[i]) {
        
            
672
                        sieve[i] = i;
        
            
673
                        <b>for</b> (<b>int</b> j = i*i; j &lt; size; j += i) {
        
            
674
                            sieve[j] = i;
        
            
675
                        }
        
            
676
                    }
        
            
677
                }
        
            
678
                <b>return</b> sieve;
        
            
679
            }</code></pre>
        
            
680
                    </section>
        
            
681
                    <section>
        
            
682
                        <h2>Algoritmi care folosesc Ciurul lui Eratostene</h2>
        
            
683
                        <h3>Lista numerelor prime</h3>
        
            
684
                        <p>
        
            
685
                            Pur și simplu generăm Ciurul lui Eratostene și apoi memorăm
        
            
686
                            care indici din el au valoarea 0.
        
            
687
                        </p>
        
            
688
            <pre><code>vector&lt;<b>int</b>&gt; all_prime_numbers(vector&lt;<b>int</b>&gt; <b>const</b> &amp;is_prime) {
        
            
689
                vector&lt;<b>int</b>&gt; prime_numbers;
        
            
690
                <b>for</b> (<b>int</b> i = 0; i &lt; is_prime.size(); ++i) {
        
            
691
                    <b>if</b> (is_prime[i]) {
        
            
692
                        prime_numbers.push_back(i);
        
            
693
                    }
        
            
694
                }
        
            
695
                <b>return</b> prime_numbers;
        
            
696
            }</code></pre>
        
            
697
                        <h3>Descompunerea în factori primi</h3>
        
            
698
                        <p>
        
            
699
                            Ne amintim că, pentru a descompune în factori primi un număr,
        
            
700
                            căutam cu un toți factorii primi ai acestuia, folosind un
        
            
701
                            <code><b>for</b></code> pentru a-i căuta. Problema este că,
        
            
702
                            dintre numerele naturale, puține sunt numere prime, și nu
        
            
703
                            are sens să le parcurgem pe toate când ne interesează doar
        
            
704
                            numerele prime.
        
            
705
                        </p>
        
            
706
            <pre><code>vector&lt;<b>int</b>&gt; prime_factors(vector&lt;<b>int</b>&gt; <b>const</b> &amp;prime_numbers) {
        
            
707
                vector&lt;<b>int</b>&gt; pf;
        
            
708
                <b>int</b> i = 0;
        
            
709
                <b>while</b> (i &lt; prime_numbers.size()
        
            
710
                       &amp;&amp; prime_numbers[i]*prime_numbers[i] &lt;= x
        
            
711
                       &amp;&amp; x != 1) {
        
            
712
                    <b>int const</b> d = prime_numbers[i];
        
            
713
                    <b>if</b> (!(x % d)) {
        
            
714
                        pf.push_back(d);
        
            
715
                        <b>do</b> {
        
            
716
                            x /= d;
        
            
717
                        } <b>while</b> (!(x % d));
        
            
718
                    }
        
            
719
                    ++i;
        
            
720
                }
        
            
721
                <b>if</b> (x != 1) {
        
            
722
                    pf.push_back(x);
        
            
723
                }
        
            
724
                <b>return</b> pf;
        
            
725
            }</code></pre>
        
            
726
                        <p>
        
            
727
                            Acest algoritm poate descompune numere până la pătratul
        
            
728
                            limitei ciurului.
        
            
729
                        </p>
        
            
730
                        <h3>Descompunerea rapidă în factori primi a numerelor mai mici</h3>
        
            
731
                        <p>
        
            
732
                            Să considerăm că ciurul are dimensiunea de 16&#8239;777&#8239;216,
        
            
733
                            sau 2<sup>24</sup>, o dimensiune rezonabilă (ocupă 16 megaocteți,
        
            
734
                            în contextul în care acum în majoritatea problemelor de concurs
        
            
735
                            se oferă 32&#8211;256 MB).
        
            
736
                        </p>
        
            
737
                        <p>
        
            
738
                            Pentru această dimensiune putem descompune în factori primi orice
        
            
739
                            număr de până la pătratul ei, adică 2<sup>48</sup>, adică
        
            
740
                            281&#8239;474&#8239;976&#8239;710&#8239;656, adică orice număr
        
            
741
                            natural cu până la 14 cifre zecimale.
        
            
742
                        </p>
        
            
743
                        <p>
        
            
744
                            Dacă nu avem nevoie de descompunerea numerelor atât de mari, putem
        
            
745
                            lucra cu un algoritm mai eficient. Acesta este un algoritm în care
        
            
746
                            numărul de operații e proporțional cu suma exponenților factorilor primi.
        
            
747
                            Dacă algoritmul anterior are ca număr maxim de pași numărul de numere
        
            
748
                            prime disponibile, acesta are ca număr maxim de pași suma exponenților.
        
            
749
                            Pentru numere de până la 2<sup>24</sup>, suma exponenților e maxim 23
        
            
750
                            (se obține chiar folosind doar factori de 2, care cresc cel mai lent).
        
            
751
                        </p>
        
            
752
            <pre><code>vector&lt;<b>int</b>&gt; prime_factors(vector&lt;<b>int</b>&gt; <b>const</b> &amp;min_pf) {
        
            
753
                vector&lt;<b>int</b>&gt; pf;
        
            
754
                <b>int</b> last_factor = -1;
        
            
755
                <b>while</b> (x != 1) {
        
            
756
                    <b>if</b> (last_factor != min_pf[x]) {
        
            
757
                        pf.push_back(min_pf[x]);
        
            
758
                        last_factor = min_pf[x];
        
            
759
                    }
        
            
760
                    x /= min_pf[x];
        
            
761
                }
        
            
762
                <b>return</b> pf;
        
            
763
            }</code></pre>
        
            
764
                        <p>
        
            
765
                            Acest algoritm se folosește de tehnica precedentă pentru a genera
        
            
766
                            factorul prim minim. Dacă numărul nu este 1, luăm acest factor prim
        
            
767
                            și sărim la numărul fără factorul prim.
        
            
768
                        </p>
        
            
769
                    </section>
        
            
770
                </body>
        
            
771
            </html>
        
            
772