[Chicago] Prime Number Generator

[T Wegner]

#!usr/bin/env python3
# PrimeNumGenSimple.py
# 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

class PrimeNumberGen:
    
    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
app = PrimeNumberGen()
app.run(10000)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20090407/28b85653/attachment.htm>