# [Chicago] Prime Number Generator

T Wegner echbar137 at yahoo.co.in
Tue Apr 7 15:44:12 CEST 2009

```#!usr/bin/env python3
# Prime number generation by construction.
# No division, two loops, just addition.
# April 2009
# Define P(n) to be the nth prime number, e.g.
# P(1) = 2, P(2) = 3, P(3) = 5, ...
# If the state of the first m Modulo objects means
# { self.modList[0].state, self.modList[1].state, ... ,
#   self.modList[m-1].state },
# then the state of the first m Modulo objects have a period of
# P(1) x P(2) x ... P(m) in N, where N in traditional algorithms
# would be the number being tested for primacy".
# This observation leads to an optimization in
# memory resources, to be implemented in a future version.
class Modulo:
isPrime = True

def __init__(self, mod):
self.mod   = mod - 1
self.state = 0

def flip(self):
self.state += 1

if self.state > self.mod:
self.state = 0
Modulo.isPrime = False

def __init__(self):
self.Modulos = [Modulo(2)]
self.n = 2

def step(self):
for i in range(0, len(self.Modulos)):
self.Modulos[i].flip()

def run(self, count):
primeCount = 1
while True:
Modulo.isPrime = True
self.step()
self.n += 1
if Modulo.isPrime:
print(self.n)
self.Modulos.append(Modulo(self.n))
primeCount += 1
if primeCount > count:
break