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! 🙂

Marina Mele has experience in artificial intelligence implementation and has led tech teams for over a decade. On her personal blog (marinamele.com), she writes about personal growth, family values, AI, and other topics she’s passionate about. Marina also publishes a weekly AI newsletter featuring the latest advancements and innovations in the field (marinamele.substack.com)