M4 L3 info Divizibilitate, numere prime - InfoMega

Un număr întreg d se numește divizor al lui n dacă expresia n%d==0 adică restul împărțirii lui n la d este egal cu zero. Numerele întregi 1 și n se numesc divizori improprii ai lui n. Oricare alt număr 1<d<n ce satisface condiția n%d==0 se numește divizor propriu al lui n.

Găsirea divizorilor lui n se referă la găsirea divizorilor proprii ai lui n și atunci când n nu are divizori proprii spunem că n este număr prim.

Algoritmul cel mai simplu:

Se observă că toți divizorii lui n sunt între 1 și n, inclusiv. Putem parcurge numerele din acest interval și verifica dacă sunt într-adevăr divizori ai lui n:

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int d =1 ; d <= n ; d ++ )
        if(n % d == 0)
            cout << d << " ";
    return 0;
}

De exemplu, pentru n = 24 se va afișa:

24
1 2 3 4 6 8 12 24
Process returned 0 (0x0)   execution time : 2.381 s
Press any key to continue.

Unde 1 și 24 sunt divizori improprii iar 2,3,4,6,8,12 sunt divizori proprii ai lui 24.

Dacă testăm acest program pentru un număr mare cum ar fi un miliard obținem:

1000000000
1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000 1000000000
Process returned 0 (0x0)   execution time : 7.456 s
Press any key to continue.

Un algoritm intermediar:

Observăm că pentru orice n, de la n/2 la n nu mai sunt divizori. Putem astfel să înjumătățim intervalul în care căutăm divizorii. Astfel înjumătățim și timpul de execuție:

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int d =2 ; d <= n/2 ; d ++ )
        if(n % d == 0)
            cout << d << " ";
    return 0;
}

De exemplu, pentru n = 24 se va afișa:

24
2 3 4 6 8 12
Process returned 0 (0x0)   execution time : 2.151 s
Press any key to continue.

Unde 2,3,4,6,8,12 sunt divizori proprii ai lui 24.

Dacă testăm acest program pentru un număr mare cum ar fi un miliard obținem:

1000000000
2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3906250 4000000 5000000 6250000 7812500 8000000 10000000 12500000 15625000 20000000 25000000 31250000 40000000 50000000 62500000 100000000 125000000 200000000 250000000 500000000
Process returned 0 (0x0)   execution time : 6.466 s
Press any key to continue.

Observăm timpul de execuție mai mic în cazul celui de-al doilea algoritm testat.

Un algoritm consacrat:

Referitor la găsirea divizorilor observăm că pentru a determina divizorii lui n este suficient să parcurgem numerele de la 1 la √n unde radical din n îl definim ca d*d pentru că divizorii sunt întotdeauna pereche.

Un caz special îl constituie pătratele perfecte. În cazul lor trebuie evitată analizarea de două ori a lui √n, care este divizor al lui n unde radical din n îl definim ca d*d.

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    for(int d =1 ; d * d <= n ; d ++ )
        if(n % d == 0)
        {
            cout << d << " ";
            if(d * d < n) // dacă d != sqrt(n) adică d != n / d
                cout << n / d << " ";
        }
    return 0;
}

Explicație:

Determinarea și afișarea divizorilor:

for (d = 1;  d * d <= n;  d++)

Se parcurg numerele de la 1 până la radical din n deoarece d*d<=n.

if(n % d == 0)

Dacă n se împarte exact la d, înseamnă că d este un divizor și se afișează cout << d << ” „; apoi

Afișarea și a celuilalt divizor n/d, dacă este diferit:

if(d * d < n){
    cout << n/d << " ";
}

Dacă d * d < n, atunci n/d este diferit de d și trebuie afișat.

De exemplu, pentru n = 12, dacă d = 2, atunci 12 / 2 = 6, deci 6 este și el un divizor.

Dati nr. 12
1 12 2 6 3 4

De exemplu, pentru n = 24 se va afișa:

24
1 24 2 12 3 8 4 6
Process returned 0 (0x0)   execution time : 1.850 s
Press any key to continue.

Dacă testăm acest program pentru un număr mare cum ar fi un miliard obținem:

1000000000
1 1000000000 2 500000000 4 250000000 5 200000000 8 125000000 10 100000000 16 62500000 20 50000000 25 40000000 32 31250000 40 25000000 50 20000000 64 15625000 80 12500000 100 10000000 125 8000000 128 7812500 160 6250000 200 5000000 250 4000000 256 3906250 320 3125000 400 2500000 500 2000000 512 1953125 625 1600000 640 1562500 800 1250000 1000 1000000 1250 800000 1280 781250 1600 625000 2000 500000 2500 400000 2560 390625 3125 320000 3200 312500 4000 250000 5000 200000 6250 160000 6400 156250 8000 125000 10000 100000 12500 80000 12800 78125 15625 64000 16000 62500 20000 50000 25000 40000 31250 32000
Process returned 0 (0x0)   execution time : 4.674 s
Press any key to continue.

Observații

Numerele care nu sunt pătrate perfecte au număr par de divizori.
Singurele numere cu număr impar de divizori sunt pătratele perfecte.
Cel mai mic divizor propriu al unui număr natural (diferit de 1 și de numărul însuși) este număr prim.