Algoritm low-memory pentru numere prime

Autor: Pirnog Theodor Ioan
Colegiul Național “B. P. Hasdeu”, Buzău

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>, în cazul în care avem de verificat mai multe numere până într-o anumită limită, dacă sunt prime. 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:

bool prime(int x){
	if(x == 0 || x == 1)
    	 return 0; //daca x = 0 sau x = 1, 
                   //atunci, cu siguranta nu este prim
        else {
		for(int i = 2; i * i <= x; i++) 
            /* cel mai mic divizor
            natural, diferit de 1, al unui numar poate fi 2,
            iar i * i <= x <=> i <= sqrt(x), întrucât,
            de la rădăcina pătrată a lui x, divizorii se 
            schimbă între ei.

            De ex: fie x = 64 => x = 
            = 1 * 64
            = 2 * 32
            = 4 * 16
            = 8 * 8, 8 = sqrt(x)
            = 16 * 4
            = 32 * 2
            = 64 * 1
        */
        	if(x % i == 0)
            	return 0;
	}
    return 1;
}

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, x = 6k + 2 sau x = 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:

bool prime(int x) {
    
    if (x <= 3)
        return x >= 2;
    /* 
        dacă x ≤ 3, x = prim, înseamnă că
        x = 2 sau x = 3 => x ≤ 3 && x ≥ 2.
    */
    if (x % 2 == 0 || x % 3 == 0)
        return 0; // eliminăm multiplii de 2 și 3, conform (1) si (2)
    for (int d = 5; d * d <= x; d += 6)
    /*
        generăm toți termenii aflați pe prima poziție 
        în perechile (6k - 1, 6k + 1) (3)
    */
        if (x % d == 0 || x % (d + 2) == 0)
        /*
            dacă d = 5, d + 2 = 7,
            dacă d = 11, d + 2 = 13, deci obținem perechile de la (3)
        */
            return 0;

    return 1;
}

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!

---