A prime number is a natural number greater than one with no positive divisors besides one and itself. The sequence begins 2, 3, 5, 7, and 11. section 5.16
The Sieve of Eratosthenes finds primes by striking out multiples of each discovered prime. A compact lazy Python version tests each candidate against the primes already found. section 5.16
When counting marks becomes arithmetic
Encode each number with that many contiguous @ symbols. Thus primes4 represents 2, 3, 5, and 7; primes5 extends the prefix with 11. By contrast, fail1 skips 5, while fail2 includes 4. The puzzle asks whether regular expressions can recognize every valid ascending initial prefix of the prime sequence. section 5.16
This is a useful trap for confident pattern matching. Lookahead assertions may resemble the sieve, but resemblance is not an implementation. The proposed regular expression does not reliably express primality; its explanation also confuses positive and negative lookahead and may match only limited arrangements of @ symbols. section 5.16 section 5.18
def get_primes():
"Simple lazy Sieve of Eratosthenes"
candidate = 2
found = []
while True:
if all(candidate % prime != 0 for prime in found):
yield candidate
found.append(candidate)
candidate += 1
Inspect the lazy Sieve implementation to compare explicit divisibility testing with the much less trustworthy regex candidate. section 5.16
