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. Prirodni brojevi koji su veći od broja 1 a nisu prosti brojevi nazivaju se složenim brojevima. Na primjer, 5 je prost broj jer je djeljiv samo s 1 i 5, a 6 je složeni broj jer osim što je djeljiv s 1 i 6 dodatno može biti podjeljen s brojevima 2 i 3.