Articole

PIRNOG THEODOR IOAN
Colegiul Național “B. P. Hasdeu”, 10A

Determinarea primalității unui număr reprezintă o sarcină de lucru pe care o putem întâlni atât la probleme simple, cât și la probleme cu un grad ridicat de dificultate, cum ar fi cele de olimpiadă. Este foarte important să observăm resursele disponibile atunci când rezolvăm o astfel de problemă. În cazul în care avem destulă memorie la dispoziție, putem utiliza ciurul lui Eratostene, fie el sub forma unui vector bool, fie utilizând <bitset>. Există însă cazuri în care memoria nu ne permite să folosim astfel de structuri, prin urmare, vom fi nevoiți să ne gândim la o altă metodă pentru determinarea primalității unui număr. Probabil că, mulți vor tinde să utilizeze următorul algoritm: (Vezi poza I)

Este un algoritm simplu, ușor de înțeles, dar care nu este foarte eficient. Avem nevoie de ceva mai bun.

Orice număr întreg, x ∈ ℤ, îl putem scrie sub forma 6k + p, unde p ∈ {-1, 0, 1, 2, 3, 4}, k ∈ ℤ. Acest lucru ne va ajuta foarte mult. Să ne folosim de acestă informație:

• dacă p ∈ {0, 2, 4}, atunci x = 6k, 6k + 2 sau 6k + 4 <=> x = 2 * 3k, x = 2 * (3k + 1) sau x = 2 * (3k + 2) => x este divizibil cu 2 => x nu este prim. (1)

• dacă p ∈ {3}, atunci x = 6k + 3 <=> x = 3 * (2k + 1) => x este divizibil cu 3 => x nu este prim. (2)

Rămânem, deci, cu p = ± 1 => x = 6k ± 1, despre care dorim să aflăm dacă este prim. Haideți să aruncăm o privire asupra perechilor de forma (6k – 1, 6k + 1), k ≥ 1: (5, 7), (11, 13), (17, 19), (23, 25), … Pentru aceste numere, vom încerca să găsim divizori pentru a verifica dacă sunt numere prime sau nu. Divizorii acestor numere vor fi tot de forma 6k ± 1, întrucât, dacă x ar fi divizibil cu un număr scris sub forma (1), atunci ar fi multiplu de 2, deci nu poate fi prim (analog pentru multiplii de 3, conform a ceea ce am zis la (2)). Observăm că, modulul diferenței dintre cei 2 termeni ai unei perechi (6k – 1, 6k + 1), k ≥ 1, este mereu 2, iar modulul diferenței dintre oricare 2 termeni aflați pe prima poziție în perechi consecutive va fi mereu 6, datorită 6k. De observat este că, numerele prime 2 și 3 nu pot fi scrise sub forma 6k – 1 sau 6k + 1, k ≥ 1, deci va trebui să ne ocupăm separat de ele. Acestea fiind spuse, să aruncăm o privire asupra noului test de primalitate: (Vezi poza II)

O problemă care necesită un astfel de algoritm este #hard_prime , în care soluția se încadrează în timp și memorie folosind acest algoritm. Spor la lucru!