Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)

Dându-se un număr natural n, să se afișeze pe ecran cel mai mic (sau mare) divizor prim al tuturor numerelor de la 1 la n.

Exemplu. Pentru n = 10, divizorii primi cei mai mici ale numerelor de la 1 la n sunt -, 2, 3, 2, 5, 2, 7, 2, 3, 2(1 nu are divizori primi, 2 are cel mai mic divizor 2, 3 are cel mai mic divizor 3, etc.).

Vom prezenta o metodă ce se bazează pe algoritmul ciurului lui Eratostene.

Ciurul lui Eratostene este un algoritm important care ia numeroase forme, însă la bază poate să determine pentru orice număr de la 1 la n, care sunt prime.

Putem să adaptăm un pic algoritmul: pentru numărul curent i, dacă este prim, vom lua toți multiplii săi j, și vom spune modifica cel mai mic sau cel mai mare divizor prim al lui n.

Cel mai mic divizor prim al numerelor de la 1 la n

Asumăm pentru început că cel mai mic divizor prim al tuturor numerelor sunt chiar ele însuși. Iterăm printre numerele prime (cele care au cel mai mic divizor prim egal cu ele însuși). Când găsim un astfel de număr i, îi luăm multiplii săi (numiți j) și verificăm dacă aceste numere au fost modificate sau nu (adică dacă încă au elementul din ciur egale cu ele însuși). Pentru cele care nu au fost modificate încă (adică numerele neprime — deoarece sunt multipli de i —, dar în ciur încă nemodificate), vom seta în ciur elementul i, marcând faptul că am găsit cel mai mic divizor prim al numărului j. Dacă mai găsim în viitor un alt număr care îl are pe j ca multplu, nu îi mai putem modifica valoarea.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                if(ciur[j] == j)
                    ciur[j] = i;
        }

    //Afișăm la final cel mai mic divizor prim al numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Cel mai mare divizor prim al numerelor de la 1 la n

Asumăm pentru început că cel mai mare divizor prim al tuturor numerelor sunt chiar ele însuși. Iterăm printre numerele prime (cele care au cel mai mare divizor prim egal cu ele însuși). Când găsim un astfel de număr i, îi luăm multiplii săi (numiți j) și setăm valoarea din ciur la i. Deoarece luăm i-urile crescătoare, de fiecare dată când modificăm valoarea ciur[j], numărul nou este garantat să fie mai mare — astfel vom găsi cel mai mare divizor prim.

#include <iostream>

using namespace std;

//Ne declarăm ciurul
int ciur[1001];

int main()
{
    //Declarăm și citim n
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        ciur[i] = i; //La început, asumăm că elementul i are cel mai mic divizor prim pe el însuși

    for(int i = 2; i <= n; i++) //Pentru toate numerele de la 2 la n
        if(ciur[i] == i) { //Elementul i este prim
            for(int j = 2 * i; j <= n; j += i) //Luăm toți multipli numărului, mai mici sau egali cu n
                ciur[j] = i;
        }

    //Afișăm la final cel mai mare divizor prim al numerelor de la 1 la n
    for(int i = 1; i <= n; i++) {
        cout << ciur[i] << " ";
    }
    return 0;
}

Alte resurse sau bibliografie

• PbInfo: Ciurul lui Eratostene
• 100din100: Ciurul lui eratostene - generarea numerelor prime - olimpiada C++
• InfoArena: Ciurul lui Eratostene