NUMERE PRIME

Cum identificam un numar prim ?

Daca un numar:

este par, nu este prim, pentru ca este divizibil cu 2;

are suma cifrelor multiplu de 3, nu este prim, deoarece este divizibil cu 3;

are ultima cifra 0 sau 5, nu este prim, deoarece este divizibil cu 5;

Metoda:

se verifica daca numarul respectiv este divizibil cu 2; 3 sau cu 5. Daca este divizibil cu unul dintre aceste numere, inseamna ca numarul este compus si te opresti. Nu continui impartirile! Daca nu este divizibil cu nici unul dintre aceste numere se continua prin impartiri cu numere prime consecutive, in ordine, de la numarul prim 7 spre cel mai mare(din ciurul lui Eratostene). Daca la una din impartiri se obtine restul zero, te opresti , inseamna ca este divizibil cu acel numar si deci nu este prim, ci compus. Daca obtii, de fiecare data, restul diferit de zero, atunci impartirile continua, pana cand la o impartire obtii catul egal cu impartitorul si restul diferit de zero(te opresti) sau catul mai mic decat impartitorul si restul diferit de zero. In aceasta situatie numarul este prim .

Exemple:

. 848 nu este prim, deoarece este par;

. 1251 nu este prim, deoarece 1 + 2 + 5 + 1 = 9 ; 3/ 9 si deci 3/ 1251.

. 375 nu este prim, deoarece este divizibil cu 5;

Sa verificam numarul 2807 :

nu este par, nu este divizibil cu 2;

2 + 8 + 7 = 17, 17 nu este divizibil cu 3, deci nu este divizibil cu 3;

ultima cifra nu este nici 0 , nici 5, nu este divizibil cu 5;

2807 = 7 · 401, restul este 0, deci numarul este divizibil cu 7 . Ne oprim; numarul nu este prim, este compus.

Sa verificam numarul 1549:

nu este par, nu este divizibil cu 2;

3 nu divide 19; 3 nu divide 1549;

Ultima cifra nu este nici 0 si nici 5, nu este divizibil cu 5;

continuam prin impartiri succesive:

1549 7 1549 = 7 · 221 + 2 ; 1549 11

14 221 11 140

221 > 7 =44 1549 = 11· 140 + 9

14 44

= =9 nu putem spune = = 9 140 > 11

7 ca este prim, 0 nu putem spune ca este

2 nici compus ; prim, nici compus;

1549 17

119 153 91

1549 = 13 · 119 + 2; = =19 1549 = 17∙ 91 + 2

119 > 13 = 91 > 17

nu putem spune

ca este prim, nici compus; nu putem spune ca este prim,

nici compus;

1549 19 1549 23

152 81 138 67

81 > 19 8 67 > 23

nu putem spune ca este prim, nu putem spune ca este prim,

nici compus; nici compus;

1549 31

= =99 1549 = 29 · 53 + 18; =309 1549 = 31· 49 + 30

53 > 29 30 49 > 31

nu putem spune ca este

nu putem spune ca este prim,    prim, nici compus;

nici compus;

1549 = 41∙ 37 + 32

41 > 37    =32 32 = 0

37 < 41

nu putem spune ca este prim,

nici compus Da, acum putem spune

ca este numar prim

am obtinut catul mai mic

decat impartitorul si restul

diferit de 0.

Pentru a sti ( mai exact) , unde ne oprim cu impartirile, procedam in felul urmator:

Cautam primul patrat perfect cu radacina numar prim mai mare decat 1549 :

Observam ca: 1549 = 39² + 28. Primul patrat perfect cu radacina numar prim este 1681( cu radacina numarul prim 41). Inseamna ca ultima impartire trebuie sa se opreasca la impartirea cu 41.

In general:

Daca, dupa ce gasesti primul patrat perfect cu radacina numar prim mai mare decat numarul dat, numerele prime mai mici decat acest numar nu divid acel numar, atunci putem spune ca numarul este prim. Daca unul dintre aceste numere prime mai mici decat patratul perfect cu radacina numar prim divide numarul, atunci numarul este compus.

Exemple:

. 529 este prim sau este compus?

Primul patrat perfect cu radacina numar prim este 841 care are radacina 29.

0bservam ca 529 este divizibil cu 23(primul numar prim mai mic decat 29) si deci nu este prim.

. 317 este prim sau este compus?

Primul patrat perfect mai mare decat 317 si care are radacina numar prim este

361 cu radacina numarul prim, 19 . Inseamna ca, daca este numar prim, impartirea trebuie sa se opreasca la impartirea cu 19. Se verifica daca numarul este divizibil cu numerele prime mai mici decat 19, fie in sens invers, fie cum am demonstrat mai sus.