Prost broj

Izvor: Wikipedija

Prosti brojevi ili prim-brojevi su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom, a veći od broja 1.

[uredi] Čemu nam prosti brojevi služe?

Prosti nam brojevi služe za rastavljanje složenih brojeva (onih koji nisu prosti) na prim-faktore.

Svaki složeni broj može se na jedinstven način rastaviti na prim-faktore.

  125|5      34|2
   25|5      17|17
    5|5       1 
    1
  
  125=5*5*5   34=2*17

[uredi] Kako rastaviti složene brojeve na prim-faktore?

Dijeljenjem s prim-brojevima, no ako znamo neka jednostavna pravila to rastavljanje postaje vrlo jednostavno.

Ako je broj paran (zadnja znamenka mu je 2, 4, 6, 8 ili 0) onda je djeljiv s brojem 2.

Ako broj završava znamenkama 5 ili 0 onda je djeljiv s brojem 5.

Ako mu je zbroj znamenaka djeljiv s 3, onda je taj broj djeljiv s 3.