غربال اراتوستنس
غربال اراتوستنس الگوریتمی ساده و قدیمی برای یافتن همه‌ی اعداد اول تا عدد صحیح برگزیده است. این الگوریتم پیش از غربال آتکین، که سریع‌تر و پیچیده‌تر بود، مورد استفاده قرار می‌گرفت. غربال اراتوستنس را اراتوستنس، ریاضیدان یونان باستان در قرن سوم پیش از میلاد ابداع کرد.
عدد اول(انگلیسی: Prime number) عددی طبیعی(Natural number) است که بر هیچ عددی بجز خود و عدد ۱ بخش‌پذیر نباشد. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگرعددی طبیعی وبزرگ‌تر از ۱ اول نباشد مرکب است. علامت اختصاری این اعداد است.
رقم یکان اعداد اول بزرگ‌تر از ۱۰ فقط ممکن است ارقام ۱، ۳، ۷، و ۹ باشد.
پیدا کردن ضابطه‌ای جبری برای اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها دست نیافته است.
دنبالهٔ اعداد اول به این صورت شروع می‌شود:
۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹، ۲۳، ۲۹، ۳۱، ۳۷، ۴۱، ۴۳، ۴۷، ۵۳، ۵۹، ۶۱، ۶۷، ۷۱، ۷۳، ۷۹، ۸۳، ۸۹، ۹۷، ۱۰۱، ۱۰۳، ۱۰۷، ۱۰۹، ۱۱۳،۱۲۷، ۱۳۱، ۱۳۷، ۱۳۹ (دنباله‌ی A000040در OEIS
قضیه‌ها
قضیه ۱: تعداد اعداد اول بی‌نهایت است.
به این اثبات دقت کنیداز برهان خلف استفاده می کنیم:
فرض خلف : اعداد اول متناهی است.
اعداد اول را در هم ضرب می کنیم.
P1,P2,P3,...,Pn
ضرب اعداد از Pi بزرگ‌تراست.
