Hamming number calculator

A recent mailing list post inspired this one. See the email and the code for details.

#!/usr/bin/python

# This proglet finds the first 3000 Hamming numbers, numbers with no prime
# factors greater than 5.

# It was inpired by the an email from Jonathan McKeown on a programming
# mailing list.

MAX_NUMBER = 3000

def getPrimes(maxnum):
    """Calculates all the prime numbers less than maxnum.
    
    This may not be the best algorithm to use, but I've gone for simplicity
    over elegance and performance here."""

    primes = [2]

    for number in range(2, maxnum):
        number += 1
        isPrime = 1
        for prime in primes:
            if (number % prime) == 0:
                isPrime = 0
                break
        if isPrime:
            primes.append(number)

    return primes


def getHamming(maxnum):
    """Calculates Hamming numbers from 1 to maxnum."""

    # We want all the primes less than half the maximum number except the
    # first three:
    primes = getPrimes(maxnum/2)[3:]
    hamming = []

    for number in range(maxnum):
        number += 1
        isHamming = 1
        for prime in primes:
            if prime > number:
                break
            if number % prime == 0:
                isHamming = 0
                break
        if isHamming:
            hamming.append(number)

    return hamming

print getHamming(MAX_NUMBER)

This was called "unpythonic", so it was replaced by the following, which also halves the numbers checked for primeness to only the odds.

#!/usr/bin/python

# This proglet finds the first 3000 Hamming numbers, numbers with no prime
# factors greater than 5.

# It was inpired by the an email from Jonathan McKeown on a programming
# mailing list.

MAX_NUMBER = 3000

def getPrimes(maxnum):
    """Calculates all the prime numbers less than maxnum.
    
    This may not be the best algorithm to use, but I've gone for simplicity
    over elegance and performance here."""

    primes = [2]

    [ primes.append(i) for i in xrange(3,maxnum+1,2) if not 0 in [i%j for j in primes] ]

    return primes


def getHamming(maxnum):
    """Calculates Hamming numbers from 1 to maxnum."""

    # We want all the primes less than half the maximum number except the
    # first three:
    primes = getPrimes(maxnum/2)[3:]
    hamming = []

    [ hamming.append(i) for i in xrange(1,maxnum+1) if not 0 in [i%j for j in
    primes] ]

    return hamming

print getHamming(MAX_NUMBER)

After this version, I realised that I had misread the question and calculated the Hamming numbers up to 3000 rather than the first 3000 Hamming numbers. The latter problem is more easily solved by generation rather than decimation, so that's what I tried next:

#!/usr/bin/python

# This proglet finds the first 3000 Hamming numbers, numbers with no prime
# factors greater than 5.

# It was inpired by the an email from Jonathan McKeown on a programming
# mailing list.

def getHamming(num):
    hamming = [1, 2]

    current = []
    cIdx = 0
    while len(hamming) < num:
        current.append(hamming[cIdx] * 5)
        current.append(hamming[cIdx] * 3)
        current.append(hamming[cIdx] * 2)
        cIdx += 1
        while (current[0] < current[-1]):
            if hamming[-1] != current[0]:
                hamming.append(current.pop(0))
            else:
                current.pop(0)
            if len(hamming) >= num: break
        current.sort()
    return hamming

for item in getHamming(3000):
    print item

The numbers coming out of this look smaller than those generated by others, but I'm not sure where the error is. I'll check back after the weekend.