Ang prime number ay isang natural na numero na mas malaki sa 1 na may dalawang divisor lamang: 1 at ang sarili nito. Ang mga unang prime number: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Ang 2 ang tanging pantay na prime number. Para suriin kung prime ang n, sapat na i-verify na ang n ay hindi nahahati ng anumang prime number hanggang √n. Ang Sieve of Eratosthenes ay isang mahusay na paraan para mahanap ang lahat ng prime number hanggang sa isang ibinigay na numero. Ang mga prime number ay may pangunahing aplikasyon sa cryptography at information security.