C18 - Număr prim, număr compus

---

Numere prime

Defintie

Oricare număr natural $a$, diferit de 1, are cel puțin divizorii 1 și $a$. Un număr natural mai mare decât 1, care are exact doi divizori (pe 1 și pe el însuși), se numește număr prim.

De Retinut!

Singurul număr par prim este 2.

Numerele naturale 0 și 1 nu sunt nici prime, nici compuse. Numărul natural 0 are o infinitate de divizori, toate numerele naturale nenule, iar numărul natural 1 are un singur divizor, el însuși.

---

Ciurul lui Eratostene

Algoritm 1

Ciurul lui Eratostene este un algoritm simplu și vechi de descoperire a tuturor numerelor prime până la un număr specificat.

Pașii algoritmului:

1. Scriem o listă cu toate numerele naturale de la 2 până la un număr $n$.
2. Se taie toți multiplii lui 2 din lista. Rezultă o listă cu numere tăiate și numere netăiate.
3. Următorul număr netăiat este 3. Se taie toți multiplii lui 3 din listă.
4. Se continuă acest proces cu următorul număr netăiat (5, 7, 11, ...).
5. Se repetă pasul de mai sus până când noua listă nu mai conține numere netăiate.

În lista finală toate numerele netăiate sunt prime.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Numerele prime mai mici decât 100 sunt:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

---

Descompunerea în factori primi

Algoritm 2

Orice număr natural mai mare decât 1 poate fi scris ca produs de numere prime. Acest proces se numește descompunerea în factori primi.

Pașii algoritmului:

1. Se împarte numărul la cel mai mic număr prim (2) și se notează câtul și restul.
2. Dacă restul este 0, se continuă împărțirea câtului la 2 până când restul nu mai este 0.
3. Când restul nu mai este 0, se trece la următorul număr prim (3) și se repetă pașii 1 și 2.
4. Se continuă acest proces cu următoarele numere prime (5, 7, 11, ...) până când câtul devine 1.

Atentie!

Daca un număr este prim, descompunerea sa în factori primi este el însuși.

Când vrem sa demonstrăm că un număr este prim, încercăm să împărțim numărul dat succesiv la toate numerele naturale prime, luate în ordine crescătoare, până când obținem câtul mai mic decât împărțitorul

Exemplu: Descompunerea numărului 60 în factori primi

1. 60 este par, deci îl împărțim la 2:
   $60 : 2 = 30$ rest $0$
2. 30 este par, deci îl împărțim la 2:
   $30 : 2 = 15$ rest $0$
3. 15 nu este par, deci îl împărțim la 3:
   $15 : 3 = 5$ rest $0$
4. 5 este prim, deci îl împărțim la 5:
   $5 : 5 = 1$ rest $0$

Am ajuns la 1, deci procesul se oprește.

Exemplu 2: Descompunerea numărului 83 în factori primi

1. 83 nu este par, deci îl împărțim la 3:
   $83 : 3 = 27$ rest $2$

83 nu este divizibil cu 5:
$83 : 5 = 16$ rest $3$

83 nu este divizibil cu 7:
$83 : 7 = 11$ rest $6$

83 nu este divizibil cu 11: $83 : 11 = 7$ rest $6$

$7<11$, deci ne oprim aici.

Am încercat toți divizorii primi mai mici sau egali cu 41 (jumătate din 83) și niciunul nu divide 83, deci 83 este prim.

---

Numere compuse

Defintie

Oricare număr natural $a$, diferit de 1, care are cel puțin trei divizori, se numește număr compus.

Exemplu:

Enunt

Pentru a arăta că un număr este compus este suficient să găsim un divizor propriu al acestuia.

a) 111 este număr compus deoarece 1+1+1=3 ⋮ 3.

b) 707 este număr compus deoarece observăm ușor că 707 ⋮ 7

c) 131313 este număr compus deoarece observăm ușor că 131313 ⋮ 13