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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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! 🙂

Please, add

+Marina Melein your comments. This way I will get a notification email and I will answer you as soon as possible! :-)