Šta su prosti brojevi i koliko ih ima?

Problem prostih brojeva često zvuči kao jednostavan ali je na njemu veoma naporno raditi, što matematičarima predstavlja veliki izazov kome je teško odoleti.

Šta su prosti brojevi?

Prost broj je onaj broj koji je deljiv samo sa jedinicom ili sam sa sobom.  Na primer broj 13= 13×1, što znači da je broj 13 nije deljiv ni sa jednim broj sem sam sa sobom, tj. ne može se predstaviti kao proizvod neka druga dva broja. To nam jasno ukazuja da je broj 13 prost broj. Za razliku od njega na primer broj 15=3×5, što nam govori da 15 nije prost broj.

Da li postoji način da se unapred odredi koji je broj prost?

Ne postoji način da se unapred odredi koji je broj prost a koji nije. Sa sigurnošću se jedino može reći koji broj NIJE prost. Svaki broj , bez obzira koliko je dugačak, a koji se završava sa 2,4,5,6,8 ili 0 ili čiji je zbir (suma) svih cifara deljiv sa 3, nije prost broj. Medjutim, ako se neki broj završava sa 1,3,7 ili 9, a zbir cifara nije deljiv sa 3 , može biti prost broj a i ne mora. Ne postoji formula koja bi nam pomogla. Ostaje samo da probamo da li možemo da dobijemo neki dati broj kao proizvod neka dva manja.

Kako pronaći proste brojeve?

Jedan od  načina da se pronadju prosti brojevi je taj da se napravi spisak svih brojeva , počevši od 2 pa nadalje, na pr.do 100. Prvi broj je 2 i on je prost. Preskočimo ga i  precrtamo svaki drugi broj sa liste: 4,6,8,10,12… Na taj način smo eliminisali sve brojeve koji su deljivi sa 2- to znači da oni nisu prosti brojevi. Sledeći broj u tabeli posle 2 je broj 3.

On je sledeći prosti pa preskačemo i njega, a precrtavamo svaki treći sa liste i tako eliminišemo sve brojeve deljive sa 3. Sledeći neprecrtani broj na listi je 5, a mi nastavimo da precrtavamo svaki  peti sledeći broj i eliminišemo brojeve deljive sa 5. Sledeći je 7 pa precrtavamo svaki sedmi. Sledeći je 11 pa svaki jedanaesti, onda 13 i tako redom.

Iz ovoga dobijamo da u prvih 100 brojeva ima tačno 25 prostih i to su:

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

Kada će svi brojevi biti precrtani?

To se neće desiti jer uvek će biti neki prost broj koji je uspeo da izbegne prethodna precrtavanja. Još 300.godine pre Hrista , grčki matematičari Euklid i Eratosten su nam pokazali da uvek postoji neki veći prost broj od onog kojeg smo pronašli bez obzira koliko daleko išli.

Zanimljivo je da ako uzmemo da prvih hiljadu uzastopnih brojeva ima 168 prostih, drugih hiljadu brojeva  ima 135 prostih, trećih 127, četvrtih 120, petih 119, i šestih 114 prostih može se pomisliti da prosti opadaju sa svakim blokom od 1000 sledećih brojeva. Ali to nije tačno jer u sledeća 4 bloka od po 1000 brojeva imamo da je u sedmom 117 prostih brojeva, u osmom 107, u devetom 110 a u desetom 112. Tako vidimo da broj prostih brojeva ne opada sa svakim sledećim blokom od 1000 brojeva.