Prvočíslo je přirozené číslo větší než 1, které má pouze dva dělitele: 1 a sebe samo. První prvočísla jsou: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 je jediné sudé prvočíslo. Ke zjištění, zda je n prvočíslo, stačí ověřit, že n není dělitelné žádným prvočíslem do √n. Eratosthenovo síto je efektivní metoda pro nalezení všech prvočísel do daného čísla. Prvočísla mají klíčové aplikace v kryptografii a informační bezpečnosti.