Articole

1•de facut in continuare problema LaturiTriunghi data la scoala ca tema
2•de facut o animatie in Pivot Animator de 100 de cadre cu tema “Teatru”
3•de rezolvat urmatoarele probleme : -Se citeste un numar n natural. Sa se afle cifra maxima a divizorilor primi ai lui.

rezolvare 3•
#include <iostream>
using namespace std;
int main ()
{ int n,d,i,D=0,c,ma=-9; cin>>n; for (d=1; d<=n; d++) { if (n%d==0) { for (i=1; i<=d; i++) { if (d%i==0) D=D+1; } if (D==2) { while (d!=0) { c=d%10; d=d/10; if (c>=ma) ma=c; } } } } cout<<ma; return 0;
}

Introducere

Ciurul lui Eratostene reprezintă o metodă de determinare a tuturor numerelor prime mai mici sau egale cu o valoare dată, n. În practică, valoarea lui n trebuie să fie una rezonabilă, ea depinzând de restricțiile de timp și memorie aplicate problemei.

Ciurului Eratostene se aplică în felul următor – în continuare lucrăm cu n=30:

• se scriu toate numerele naturale de la 1 la n=30:

• se taie din lista numărul 1, care nu este prim

• se identifică următorul număr netăiat, 2. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta.

• se identifică următorul număr netăiat, 3. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta. Unii dintre ei au fost deja tăiați, deoarece sunt și multipli ai lui 2.

• se identifică următorul număr netăiat, 5. Acest este prim, iar din listă se vor tăia toți multipli săi, mai mari decât acesta. Unii dintre ei au fost deja tăiați, deoarece sunt și multipli ai lui 2 sau 3.

• se identifică următorul număr netăiat, 7. Acesta este prim, dar totodată 7*7>30 căutarea numerelor prime s-a încheiat. Toate numerele care nu au fost tăiate sunt prime.

Animație

Algoritm

Pentru identificarea numerelor prime într-un algoritm/program, vom folosi un vector caracteristic, v[], cu următoarea semnificație:

\( v[x]=\begin{cases} 0& \text{dacă $x$ prim},\\1& \text{dacă $x$ nu este prim}.\end{cases} \)

Vom porni de la un vector cu toate elementele nule, apoi vom marca pe rând cu 1 toate numerele care sunt multipli ai unor numere mai mici. Un algoritm pseudocod care realizează acest operații este:

pentru i←0,n execută
    V[i] ← 0
sf_pentru
V[0] ← 1
V[1] ← 1
pentru i ← 2,sqrt(n) execută
    dacă V[i] = 0 atunci
        pentru j ← 2, [n/i] execută
            V[i*j] ← 1
        sf_pentru
    sf_dacă
sf_pentru

Probleme similare

Mecanismul prin care se identifică numerele prime specific Ciurului lui Eraostene poate fi folosit și la determinarea altor rezultate. De exemplu, vrem să aflăm pentru un n dat (nu prea mare) câți divizori are fiecare număr natural din intervalul [1,n].

Pentru acesta, vom construi un vector V, în care v[x] reprezintă numărul de divizori ai lui x. Pentru a construi acest vector, vom parcurge numerele de la 1 la n, și pentru fiecare număr x vom identifica multiplii săi. Pentru fiecare y multiplu al lui x vom incrementa valoarea lui v[y].

Un algoritm pseudocod este:

pentru i←1,n execută
    V[i] ← 0
sf_pentru
pentru x ← 1,n execută
    pentru x ← x, n , x  execută
        V[y] ← V[y] + 1
    sf_pentru
sf_pentru

Teoreme fundamentală a aritmeticii:

Orice număr natural \(n\) mai mare decât \(1\) se poate scrie în mod unic sub forma \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), unde \( p_1 < p_2 < … < p_k \) sunt numere prime, iar \( e_i > 0, i=1..k \)

V-ați întrebat de ce numărul \( 1 \) nu este prim? Dacă ar fi, teorema de mai sus ar fi falsă! Pentru numărul \(12\), ar fi valabile descompunerile:

• \( 12 = 2^2 \cdot 3\)
• \( 12 = 1 \cdot 2^2 \cdot 3\)
• \( 12 = 1^7 \cdot 2^2 \cdot 3\)
• ș.a.m.d.

Iată trei aplicații interesante ale descompunerii în factori primi. Lăsăm demonstrarea lor în sarcina cititorului!

Numărul de divizori

Numărul de divizori ai lui \(n\) poate fi determinat prin numărarea acestora: parcurgerea intervalului de divizori posibili și numărarea valorilor care sunt divizori ai lui \(n\).

O altă soluție este folosirea următoarei proprietăți.

Proprietate: Pentru un număr natural care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), numărul de divizori este: \( (e_1 + 1) \cdot (e_2 + 1) \cdot … \cdot (e_k + 1) \).

Exemplu: Fie \( n = 12\). Divizorii sunt \( 1, 2, 3, 4, 6, 12\) – 6 divizori.
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( (2+1) \cdot (1+1) = 3 \cdot 2 = 6 \).

Suma divizorilor

Proprietate: Pentru un număr natural care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), suma divizorilor este: \( { {p_1^{e_1+1} -1 } \over {p_1 – 1} } \cdot { {p_2^{e_2+1} -1 } \over {p_2 – 1} } \cdot … \cdot { {p_k^{e_k+1} -1 } \over {p_k – 1} } \).

Exemplu: Fie \( n = 12\). Suma divizorilor este \(1 + 2 + 3 + 4 + 6 + 12 = 28\).
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( { {2^{2+1} -1 } \over {2 – 1} } \cdot { {3^{1+1} -1 } \over {3 – 1} } = { {2^3 -1 } \over {1} } \cdot { {3^{2} -1 } \over {2} } = { {8 -1 } \over {1} } \cdot { {9 -1 } \over {2} } = { {7 } \over {1} } \cdot { {8 } \over {2} } = {7 } \cdot {4} = 28 \).

Indicatorul lui Euler

Indicatorul lui Euler sau funcția lui Euler, sau totient se notează cu \( \varphi(n) \) (unde \(n\) este un număr natural nenul ) și \( \varphi(n) \) reprezintă numărul de numere mai mici sau egale cu \(n\) și prime cu acesta.

Valoarea lui \( \varphi(n) \) poate fi determinată prin numărarea valorilor prime cu \(n\), sau putem aplica următoarea proprietate:

Proprietate: Pentru un număr natural \(n\) care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), are loc relația: \( \varphi(n)=(p_{1}-1)p_{1}^{e_{1}-1} \cdot(p_{2}-1)p_{2}^{e_{2}-1} \cdot \cdots \cdot (p_{k}-1)p_{k}^{e_{k}-1} \).
O scriere echivalentă este: \(\varphi(n)=n \left(1-\frac{1}{p_{1}}\right) \cdot \left(1-\frac{1}{p_{2}}\right) \cdot \cdots \cdot \left(1-\frac{1}{p_{k}}\right) \)

Exemplu: Pentru \( n = 12\), numerele mai mici decât \( n \), prime cu acesta sunt: \( \text 1, 5, 7, 11\), adică \( 4 \) numere.
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( \varphi(12) = (2-1) \cdot 2^{2-1} \cdot (3-1) \cdot 3^{1-1} = 1 \cdot 2^1 \cdot 2 \cdot 3^0 = 2 \cdot 2 = 4 \).

Observaţie: Dacă \( n \) este număr prim, atunci \( \varphi(n) = n – 1 \).

Teorema lui Euler:

Dacă \(a, n\) sunt două numere naturale prime între ele, atunci:
$$ a^{ \varphi (n) } \equiv 1 \left(\mod n \right) $$

Să începem cu niște definiții – în cele ce urmează vorbim despre numere naturale:

• Spunem că numărul n divide numărul m dacă există un număr p astfel încât n * p = m. De regulă, este echivalent cu faptul că restul împărțirii lui m la n este 0, în C/C++ m % n este 0.
• Dacă n divide pe m, spunem că n este divizor al lui m, iar m este multiplu al lui n.