Prímszámok és algoritmusok

Abstract

A prímszámok fogalmát már az egyiptomiak és a mezopotámiai népek is ismerték, az első jelentősebb tanulmányozói mégis a pithagorusok voltak. Már az ókori matematikusokat is elkápráztatta a prímszámokkal kapcsolatos problémák. Az egyik alap probléma annak az eldöntése volt, hogy egy szám prímszám-e vagy sem. Euklidesz: Elemek c. könyvéből ismerhetjük, azt a bizonyítást, hogy a prímszámok száma végtelen. Az ókori görögöktől maradt fent az eratoszthenészi szita is, amit prímszámok keresésére használtak, de a nagy számok esetén meglehetősen fáradtságosnak bizonyult. Sok matematikus próbált a prímszámok előállítására formulát találni, de ezek a kísérletek nem jártak jelentős sikerrel.