[Verse 1]
Ancient Greek mathematician had a plan so clean
Eratosthenes designed a filtering machine
Start with every number from two up to N
Cross out multiples, watch the primes ascend
Two's the first prime, mark it down as true
Now eliminate four, six, eight - they're through
Move to three, it survives the filtering test
Strike out nine, fifteen, twenty-one - no rest
[Chorus]
Sieve it out, cross it off, only primes remain
Mark and sweep through the range, algorithms reign
Start at two, cross multiples, pattern's crystal clear
Sieve of Eratosthenes, prime detection here
Square root boundary, optimization tight
Sieve it out, cross it off, primes come into sight
[Verse 2]
Five's the next survivor in our number grid
Mark it prime, then cross what it forbid
Twenty-five, thirty-five, forty-five erased
Seven stays untouched, in prime position placed
Algorithm's beauty lies in systematic sweep
No division tests, just marking what to keep
Time complexity's linear with some logarithmic cost
Space efficiency preserved, no memory lost
[Chorus]
Sieve it out, cross it off, only primes remain
Mark and sweep through the range, algorithms reign
Start at two, cross multiples, pattern's crystal clear
Sieve of Eratosthenes, prime detection here
Square root boundary, optimization tight
Sieve it out, cross it off, primes come into sight
[Bridge]
Boolean array holds the truth of every slot
True means prime candidate, false means it's not
Nested loops iterate through the sieving dance
Outer loop finds primes, inner kills their chance
When P squared exceeds N, the algorithm's done
All remaining trues are primes, victory's won
[Verse 3]
Modern implementations use bit manipulation
Pack eight flags per byte, memory conservation
Wheel factorization speeds the process more
Skip even numbers except for two before
Segmented sieves handle massive number ranges
Cache-friendly access, performance never changes
From ancient Alexandria to silicon today
This sieve keeps computing primes the efficient way
[Chorus]
Sieve it out, cross it off, only primes remain
Mark and sweep through the range, algorithms reign
Start at two, cross multiples, pattern's crystal clear
Sieve of Eratosthenes, prime detection here
Square root boundary, optimization tight
Sieve it out, cross it off, primes come into sight
[Outro]
Twenty-three hundred years of algorithmic fame
Eratosthenes' sieve still plays the priming game