Prosti brojevi su neobičan skup beskonačnih brojeva, svi su cijeli (a ne razlomci ili decimalni), i svi su veći od jedan. Kada su se teorije o prostim brojevima prvi put zagovarale, broj jedan se smatrao prostim. Međutim, u modernom smislu, jedan nikada ne može biti prost jer ima samo jedan djelitelj ili faktor, broj jedan. U današnjoj definiciji prost broj ima točno dva djelitelja, broj jedan i sam broj.
Stari Grci stvorili su teorije i razvoj prvih skupova prostih brojeva, iako možda postoji i neka egipatska studija o ovom pitanju. Ono što je zanimljivo je da tema prostih brojeva nije bila puno dotaknuta niti proučavana nakon starih Grka sve do dugo nakon srednjovjekovnog razdoblja. Zatim, sredinom 17. stoljeća, matematičari su počeli proučavati proste brojeve s mnogo većim fokusom, a ovo proučavanje nastavlja se i danas, s mnogo razvijenih metoda za pronalaženje novih prostih brojeva.
Osim pronalaženja prostih brojeva, matematičari znaju da postoji beskonačan broj, iako ih nisu otkrili sve, a beskonačnost sugerira da ne mogu. Otkrivanje najvećeg premijera bilo bi nemoguće. Najbolje što matematičar može težiti je pronalaženje najvećeg poznatog prostog broja. Beskonačnost znači da će postojati još jedan, i to još jedan u beskrajnom nizu izvan onoga što je otkriveno.
Dokaz za beskonačnost prostih brojeva datira još od Euklidove studije o njima. Razvio je jednostavnu formulu po kojoj bi dva prosta broja pomnožena zajedno plus broj jedan ponekad ili često otkrili novi prosti broj. Euklidovo djelo nije uvijek otkrivalo nove proste brojeve, čak ni s malim brojevima. Evo radnih i neradnih primjera Euklidove formule:
2 X 3 = 6 +1 = 7 (novi prosti)
5 X 7 = 35 +1= 36 (broj s brojnim faktorima)
Druge metode za razvijanje prostih brojeva u antičko doba uključuju korištenje Eratostenovog sita, koje je razvijeno otprilike u trećem stoljeću prije Krista. U ovoj metodi brojevi su navedeni na mreži, a mreža može biti prilično velika. Svaki broj koji se promatra kao višekratnik bilo kojeg broja precrtava se sve dok osoba ne dosegne kvadratni korijen najvećeg broja na mreži. Ta bi sita mogla biti velika i s njima je komplicirano raditi u usporedbi s načinom na koji se prostim brojevima može manipulirati i naći danas. Danas, zbog velikog broja ljudi s kojima većina ljudi radi, računala se općenito koriste za pronalaženje novih prostih brojeva i mnogo su brža u poslu nego što ljudi mogu biti.
Još uvijek je potreban ljudski trud da se mogući prosti broj podnese mnogim testovima kako bi se osiguralo da je prost, pogotovo kada je iznimno velik. Postoje čak i nagrade za pronalaženje novih brojeva što može biti unosno za matematičare. Trenutno najveći poznati prosti brojevi imaju više od 10 milijuna znamenki, ali s obzirom na beskonačnost ovih posebnih brojeva, jasno je da će netko kasnije probiti ovaj prag.