Python scripts for prime numbers and divisors

Very recently I been interested in solving the problems proposed by Project Euler. Currently I just solved about 20 problems, but I run into some nice algorithms for finding prime numbers and divisors that I would like to share.

This first snippet defines a Python function that returns a list of the prime numbers up to a given integer. It uses the Sieve of Atkin, which is a modern algorithm that optimizes the Sieve of Eratosthenes.

File: marinamele_sieve_atkin.py
-------------------------------

import math
def atkin(nmax):
    """
    Returns a list of prime numbers below the number "nmax"
    """
    is_prime = dict([(i, False) for i in range(5, nmax+1)])
    for x in range(1, int(math.sqrt(nmax))+1):
        for y in range(1, int(math.sqrt(nmax))+1):
            n = 4*x**2 + y**2
            if (n <= nmax) and ((n % 12 == 1) or (n % 12 == 5)):
                is_prime[n] = not is_prime[n]
            n = 3*x**2 + y**2
            if (n <= nmax) and (n % 12 == 7):
                is_prime[n] = not is_prime[n]
            n = 3*x**2 - y**2
            if (x > y) and (n <= nmax) and (n % 12 == 11):
                is_prime[n] = not is_prime[n]
    for n in range(5, int(math.sqrt(nmax))+1):
        if is_prime[n]:
            ik = 1
            while (ik * n**2 <= nmax):
                is_prime[ik * n**2] = False
                ik += 1
    primes = []
    for i in range(nmax + 1):
        if i in [0, 1, 4]: pass
        elif i in [2,3] or is_prime[i]: primes.append(i)
        else: pass
    return primes
assert(atkin(30)==[2, 3, 5, 7, 11, 13, 17, 19, 23, 29])

This other snippet returns an unsorted list of all the divisors of a given integer. It has a second argument which is a list of prime numbers. Note that this list can be found using the previous atkin function.

File: marinamele_getDivisors.py
-------------------------------

def getDivisors(number, primes):
    """
    Returns an unsorted list of the divisors of 'number' using the list of prime numbers 'primes'
    """
    if number == 1: return [number,]
    if number in primes:
        return [1, number]
    divisors = []
    for p in primes:
        if number % p == 0:
            k = 1
            pdiv = []
            while (p**k < number) and (number % (p**k)) == 0:
                pdiv.append(p**k)
                k += 1
            divisors_copy = divisors[:]
            for p in pdiv:
                divisors += [pk*p for pk in divisors_copy if pk*p < number]
            divisors += pdiv
    divisors += [1, number]
    return divisors

Hope it is helpful!

And please, share any thoughts and improvements of the algorithms! 🙂