>[!abstract] >The **sieve of Eratosthenes** was invented by Greek polymath (and chief librarian at the Library of Alexandria) Eratosthenes of Cyrene (276–195 BC) as a method to quickly identify prime numbers up to some value $n$. ## Method 1. List all natural numbers from $2$ to $n$. 2. Start from the first number ($2$) in that sequence. Cross out every number at constant intervals equal to that number ($4$, $6$, $8$, etc.). 3. Find the next smallest number that remains (is not crossed out). Again cross out every number at constant intervals equal to that number. 4. Repeat step 3 until there are no more next smallest number remaining. All the remaining numbers are primes. ## Example for $n = 100$ in just four operations ### Step 1: List all natural numbers from $2$ to $n$ | | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | | ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: | ---: | ----: | | $11$ | $12$ | $13$ | $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ | | $21$ | $22$ | $23$ | $24$ | $25$ | $26$ | $27$ | $28$ | $29$ | $30$ | | $31$ | $32$ | $33$ | $34$ | $35$ | $36$ | $37$ | $38$ | $39$ | $40$ | | $41$ | $42$ | $43$ | $44$ | $45$ | $46$ | $47$ | $48$ | $49$ | $50$ | | $51$ | $52$ | $53$ | $54$ | $55$ | $56$ | $57$ | $58$ | $59$ | $60$ | | $61$ | $62$ | $63$ | $64$ | $65$ | $66$ | $67$ | $68$ | $69$ | $70$ | | $71$ | $72$ | $73$ | $74$ | $75$ | $76$ | $77$ | $78$ | $79$ | $80$ | | $81$ | $82$ | $83$ | $84$ | $85$ | $86$ | $87$ | $88$ | $89$ | $90$ | | $91$ | $92$ | $93$ | $94$ | $95$ | $96$ | $97$ | $98$ | $99$ | $100$ | ### Step 2: Cross out in intervals of $2$ | | $\textcolor{crimson}{2}$ | $3$ | $\color{crimson}{\cancel{4}}$ | $5$ | $\color{crimson}{\cancel{6}}$ | $7$ | $\color{crimson}{\cancel{8}}$ | $9$ | $\color{crimson}{\cancel{10}}$ | | ---: | -----------------------------: | ---: | -----------------------------: | ---: | -----------------------------: | ---: | -----------------------------: | ---: | ------------------------------: | | $11$ | $\color{crimson}{\cancel{12}}$ | $13$ | $\color{crimson}{\cancel{14}}$ | $15$ | $\color{crimson}{\cancel{16}}$ | $17$ | $\color{crimson}{\cancel{18}}$ | $19$ | $\color{crimson}{\cancel{20}}$ | | $21$ | $\color{crimson}{\cancel{22}}$ | $23$ | $\color{crimson}{\cancel{24}}$ | $25$ | $\color{crimson}{\cancel{26}}$ | $27$ | $\color{crimson}{\cancel{28}}$ | $29$ | $\color{crimson}{\cancel{30}}$ | | $31$ | $\color{crimson}{\cancel{32}}$ | $33$ | $\color{crimson}{\cancel{34}}$ | $35$ | $\color{crimson}{\cancel{36}}$ | $37$ | $\color{crimson}{\cancel{38}}$ | $39$ | $\color{crimson}{\cancel{40}}$ | | $41$ | $\color{crimson}{\cancel{42}}$ | $43$ | $\color{crimson}{\cancel{44}}$ | $45$ | $\color{crimson}{\cancel{46}}$ | $47$ | $\color{crimson}{\cancel{48}}$ | $49$ | $\color{crimson}{\cancel{50}}$ | | $51$ | $\color{crimson}{\cancel{52}}$ | $53$ | $\color{crimson}{\cancel{54}}$ | $55$ | $\color{crimson}{\cancel{56}}$ | $57$ | $\color{crimson}{\cancel{58}}$ | $59$ | $\color{crimson}{\cancel{60}}$ | | $61$ | $\color{crimson}{\cancel{62}}$ | $63$ | $\color{crimson}{\cancel{64}}$ | $65$ | $\color{crimson}{\cancel{66}}$ | $67$ | $\color{crimson}{\cancel{68}}$ | $69$ | $\color{crimson}{\cancel{70}}$ | | $71$ | $\color{crimson}{\cancel{72}}$ | $73$ | $\color{crimson}{\cancel{74}}$ | $75$ | $\color{crimson}{\cancel{76}}$ | $77$ | $\color{crimson}{\cancel{78}}$ | $79$ | $\color{crimson}{\cancel{80}}$ | | $81$ | $\color{crimson}{\cancel{82}}$ | $83$ | $\color{crimson}{\cancel{84}}$ | $85$ | $\color{crimson}{\cancel{86}}$ | $87$ | $\color{crimson}{\cancel{88}}$ | $89$ | $\color{crimson}{\cancel{90}}$ | | $91$ | $\color{crimson}{\cancel{92}}$ | $93$ | $\color{crimson}{\cancel{94}}$ | $95$ | $\color{crimson}{\cancel{96}}$ | $97$ | $\color{crimson}{\cancel{98}}$ | $99$ | $\color{crimson}{\cancel{100}}$ | ### Step 3.1: Cross out in intervals of $3$ | | $2$ | $\textcolor{crimson}{3}$ | $\cancel{4}$ | $5$ | $\color{crimson}{\cancel{6}}$ | $7$ | $\cancel{8}$ | $\color{crimson}{\cancel{9}}$ | $\cancel{10}$ | | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | | $11$ | $\color{crimson}{\cancel{12}}$ | $13$ | $\cancel{14}$ | $\color{crimson}{\cancel{15}}$ | $\cancel{16}$ | $17$ | $\color{crimson}{\cancel{18}}$ | $19$ | $\cancel{20}$ | | $\color{crimson}{\cancel{21}}$ | $\cancel{22}$ | $23$ | $\color{crimson}{\cancel{24}}$ | $25$ | $\cancel{26}$ | $\color{crimson}{\cancel{27}}$ | $\cancel{28}$ | $29$ | $\color{crimson}{\cancel{30}}$ | | $31$ | $\cancel{32}$ | $\color{crimson}{\cancel{33}}$ | $\cancel{34}$ | $35$ | $\color{crimson}{\cancel{36}}$ | $37$ | $\cancel{38}$ | $\color{crimson}{\cancel{39}}$ | $\cancel{40}$ | | $41$ | $\color{crimson}{\cancel{42}}$ | $43$ | $\cancel{44}$ | $\color{crimson}{\cancel{45}}$ | $\cancel{46}$ | $47$ | $\color{crimson}{\cancel{48}}$ | $49$ | $\cancel{50}$ | | $\color{crimson}{\cancel{51}}$ | $\cancel{52}$ | $53$ | $\color{crimson}{\cancel{54}}$ | $55$ | $\cancel{56}$ | $\color{crimson}{\cancel{57}}$ | $\cancel{58}$ | $59$ | $\color{crimson}{\cancel{60}}$ | | $61$ | $\cancel{62}$ | $\color{crimson}{\cancel{63}}$ | $\cancel{64}$ | $65$ | $\color{crimson}{\cancel{66}}$ | $67$ | $\cancel{68}$ | $\color{crimson}{\cancel{69}}$ | $\cancel{70}$ | | $71$ | $\color{crimson}{\cancel{72}}$ | $73$ | $\cancel{74}$ | $\color{crimson}{\cancel{75}}$ | $\cancel{76}$ | $77$ | $\color{crimson}{\cancel{78}}$ | $79$ | $\cancel{80}$ | | $\color{crimson}{\cancel{81}}$ | $\cancel{82}$ | $83$ | $\color{crimson}{\cancel{84}}$ | $85$ | $\cancel{86}$ | $\color{crimson}{\cancel{87}}$ | $\cancel{88}$ | $89$ | $\color{crimson}{\cancel{90}}$ | | $91$ | $\cancel{92}$ | $\color{crimson}{\cancel{93}}$ | $\cancel{94}$ | $95$ | $\color{crimson}{\cancel{96}}$ | $97$ | $\cancel{98}$ | $\color{crimson}{\cancel{99}}$ | $\cancel{100}$ | ### Step 3.2: Cross out in intervals of $5$ | | $2$ | $3$ | $\cancel{4}$ | $\textcolor{crimson}{5}$ | $\cancel{6}$ | $7$ | $\cancel{8}$ | $\cancel{9}$ | $\color{crimson}{\cancel{10}}$ | | ------------: | ------------: | ------------: | ------------: | -----------------------------: | ------------: | ------------: | ------------: | ------------: | ------------------------------: | | $11$ | $\cancel{12}$ | $13$ | $\cancel{14}$ | $\color{crimson}{\cancel{15}}$ | $\cancel{16}$ | $17$ | $\cancel{18}$ | $19$ | $\color{crimson}{\cancel{20}}$ | | $\cancel{21}$ | $\cancel{22}$ | $23$ | $\cancel{24}$ | $\color{crimson}{\cancel{25}}$ | $\cancel{26}$ | $\cancel{27}$ | $\cancel{28}$ | $29$ | $\color{crimson}{\cancel{30}}$ | | $31$ | $\cancel{32}$ | $\cancel{33}$ | $\cancel{34}$ | $\color{crimson}{\cancel{35}}$ | $\cancel{36}$ | $37$ | $\cancel{38}$ | $\cancel{39}$ | $\color{crimson}{\cancel{40}}$ | | $41$ | $\cancel{42}$ | $43$ | $\cancel{44}$ | $\color{crimson}{\cancel{45}}$ | $\cancel{46}$ | $47$ | $\cancel{48}$ | $49$ | $\color{crimson}{\cancel{50}}$ | | $\cancel{51}$ | $\cancel{52}$ | $53$ | $\cancel{54}$ | $\color{crimson}{\cancel{55}}$ | $\cancel{56}$ | $\cancel{57}$ | $\cancel{58}$ | $59$ | $\color{crimson}{\cancel{60}}$ | | $61$ | $\cancel{62}$ | $\cancel{63}$ | $\cancel{64}$ | $\color{crimson}{\cancel{65}}$ | $\cancel{66}$ | $67$ | $\cancel{68}$ | $\cancel{69}$ | $\color{crimson}{\cancel{70}}$ | | $71$ | $\cancel{72}$ | $73$ | $\cancel{74}$ | $\color{crimson}{\cancel{75}}$ | $\cancel{76}$ | $77$ | $\cancel{78}$ | $79$ | $\color{crimson}{\cancel{80}}$ | | $\cancel{81}$ | $\cancel{82}$ | $83$ | $\cancel{84}$ | $\color{crimson}{\cancel{85}}$ | $\cancel{86}$ | $\cancel{87}$ | $\cancel{88}$ | $89$ | $\color{crimson}{\cancel{90}}$ | | $91$ | $\cancel{92}$ | $\cancel{93}$ | $\cancel{94}$ | $\color{crimson}{\cancel{95}}$ | $\cancel{96}$ | $97$ | $\cancel{98}$ | $\cancel{99}$ | $\color{crimson}{\cancel{100}}$ | ### Step 3.3: Cross out in intervals of $7$ | | $2$ | $3$ | $\cancel{4}$ | $5$ | $\cancel{6}$ | $\textcolor{crimson}{7}$ | $\cancel{8}$ | $\cancel{9}$ | $\cancel{10}$ | | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | -----------------------------: | | $11$ | $\cancel{12}$ | $13$ | $\color{crimson}{\cancel{14}}$ | $\cancel{15}$ | $\cancel{16}$ | $17$ | $\cancel{18}$ | $19$ | $\cancel{20}$ | | $\color{crimson}{\cancel{21}}$ | $\cancel{22}$ | $23$ | $\cancel{24}$ | $\cancel{25}$ | $\cancel{26}$ | $\cancel{27}$ | $\color{crimson}{\cancel{28}}$ | $29$ | $\cancel{30}$ | | $31$ | $\cancel{32}$ | $\cancel{33}$ | $\cancel{34}$ | $\color{crimson}{\cancel{35}}$ | $\cancel{36}$ | $37$ | $\cancel{38}$ | $\cancel{39}$ | $\cancel{40}$ | | $41$ | $\color{crimson}{\cancel{42}}$ | $43$ | $\cancel{44}$ | $\cancel{45}$ | $\cancel{46}$ | $47$ | $\cancel{48}$ | $\color{crimson}{\cancel{49}}$ | $\cancel{50}$ | | $\cancel{51}$ | $\cancel{52}$ | $53$ | $\cancel{54}$ | $\cancel{55}$ | $\color{crimson}{\cancel{56}}$ | $\cancel{57}$ | $\cancel{58}$ | $59$ | $\cancel{60}$ | | $61$ | $\cancel{62}$ | $\color{crimson}{\cancel{63}}$ | $\cancel{64}$ | $\cancel{65}$ | $\cancel{66}$ | $67$ | $\cancel{68}$ | $\cancel{69}$ | $\color{crimson}{\cancel{70}}$ | | $71$ | $\cancel{72}$ | $73$ | $\cancel{74}$ | $\cancel{75}$ | $\cancel{76}$ | $\color{crimson}{\cancel{77}}$ | $\cancel{78}$ | $79$ | $\cancel{80}$ | | $\cancel{81}$ | $\cancel{82}$ | $83$ | $\color{crimson}{\cancel{84}}$ | $\cancel{85}$ | $\cancel{86}$ | $\cancel{87}$ | $\cancel{88}$ | $89$ | $\cancel{90}$ | | $\color{crimson}{\cancel{91}}$ | $\cancel{92}$ | $\cancel{93}$ | $\cancel{94}$ | $\cancel{95}$ | $\cancel{96}$ | $97$ | $\color{crimson}{\cancel{98}}$ | $\cancel{99}$ | $\cancel{100}$ | ### Step 4: All remaining numbers are prime | | $2$ | $3$ | | $5$ | | $7$ | | | | | ---: | --: | ---: | --: | --: | --: | ---: | --: | ---: | --: | | $11$ | | $13$ | | | | $17$ | | $19$ | | | | | $23$ | | | | | | $29$ | | | $31$ | | | | | | $37$ | | | | | $41$ | | $43$ | | | | $47$ | | | | | | | $53$ | | | | | | $59$ | | | $61$ | | | | | | $67$ | | | | | $71$ | | $73$ | | | | | | $79$ | | | | | $83$ | | | | | | $89$ | | | | | | | | | $97$ | | | | >[!related] >- **North** (upstream): — >- **West** (similar): — >- **East** (different): — >- **South** (downstream): —